Algorithms

Big O Notation

\> Big-O notation হচ্ছে আমাদের কোনো একটা function এর ইনপুট বাড়ার সাথে সাথে কতটা টাইম কমপ্লেক্সিটি ও কতটা স্পেস কমপ্লেক্সিটি হচ্ছে সেটা নির্ণয় করা। এটি একটি টুল যার সাহায্যে কোনো একটা অ্যালগরিদমের রানটাইমের উপর ভিত্তি করে টাইম কমপ্লেক্সিটি বের করা যায়। Big O notation কোনো অ্যালগরিদমের টাইম কমপ্লেক্সিটি ও কতটা স্পেস কমপ্লেক্সিটি নির্ণয় করতে ব্যবহৃত হয়, তাদের মধ্যে বৃদ্ধির হার হিসেবে প্রকাশিত হয়। উদাহরণস্বরূপ, O(1), O(log n), O(n), O(n log n), O(n^2) ইত্যাদি।

Big-O notation এর মাধ্যমে আমাদের প্রতিনিয়ত ব্যবহৃত কয়েকটা জাভাস্কিপ্ট মেথত এর টাইম কমপ্লেসিটি ও স্পেস কমপ্লেসিটি নির্ণয় করি

\=> Big O(n) - যখন কোনো ইনপুট আমাদের অনিশ্চিত থাকে ( মানে কতগুলো ইনপুট অথবা ভেলু থাকতে পারে অথবা আউটপুট আসতে পারে আমরা জানি না ) তখন আমরা সেটাকে n হিসেবে নেই, এবং যে সকল মেথডের টাইম কমপ্লেক্সিটি আমরা নির্ণয় করার সময় এইরকম ভাবে অনিশ্চিত ইনপুট আসতে পারে পাই সেগুলোকে আমরা Big O(n) বলি।

\=> Big O(1) - যখন কোনো ইনপুট আমাদের নিশ্চিত থাকে ( মানে আমরা জানি যে ওইটা শুধুমাত্র একটা আউটপুট দিবে আমাদের কন্ডিশন অনুযায়ী ) তখন আমরা সেটাকে 1 ধরি, এবং যে সকল মেথডের টাইম কমপ্লেক্সিটি আমরা নির্ণয় করার সময় এইরকম ভাবে নিশ্চিত ইনপুট আসতে পারে পাই সেগুলোকে আমরা Big O(1) বলি।

• Object

• Object.keys - Big O(n)

  ( এটায় Big O(n) কারণ একটি object এ অনেক keys তাকতে পারে এটা বলা মুশকিল যে ওই object এর মধ্যে মোট কতটি entries তাকবে, তাই আমরা ধরে নিলাম যে একটা n ইনপুটে থাকবে এবং সেই n এ যত ইচ্ছা দেওয়া হবে তাই এটা n এর উপর ডিপেন্ডেড এবং এর জন্যই এটা Big O(n) )

• Object.entries - Big O(n)

  ( same as object.keys )

• Object.values - Big O(n)

  ( same as object.keys )

• Object.hasOwnProperty - Big O(1)

  ( এটায় Big O(1) কারণ আমরা যখন কোনো property সার্চ করবো তখন তো আমরা একটা value ই পাবো এবং এর জন্যই এটা Big O(1) )

• Array

• push, pop - Big O(1)

  ( এটায় Big O(1) কারণ একটি array তে আমরা যখন push or pop এর মাধ্যমে কোনো element যুক্ত করি তখন সেই element টি ওই array এর শেষের দিকে যুক্ত হয় অথবা ডিলিট হয়, যার জন্য কোনো element এর ইনডেক্স পরিবর্তন করতে হয় না এবং এর জন্যই এটা Big O(1) )

• shift, unshift - Big O(n)

  ( এটায় Big O(n) কারণ একটি array তে আমরা যখন shift or unshift এর মাধ্যমে কোনো element যুক্ত করি তখন সেই element টি ওই array এর শুরুর দিকে যুক্ত হয় অথবা ডিলিট হয়, যার জন্য আগের element দের ইনডেক্স পরিবর্তন করতে হয়। তাই এখানে n বার নতুন element যুক্ত হতে পারে যার জন্যই এটা Big O(n) )

• search - Big O(n)

  ( এটায় Big O(n) কারণ একটি array তে কতগুলো value তাকবে তা বলা যাবে না এবং আমরা যদি ওই array তে কোনো কিছু search করি তাহলে আমাদের ওই array তে থাকা প্রতিটি element এর মধ্যে দিয়ে খুজতে হবে আমাদের কাংকিত element টিকে এবং সেটা n তম বার ও হতে পারে যার জন্যই এটা Big O(n) )

• access - Big O(1)

  ( এটায় Big O(1) কারণ একটি array থেকে আমরা যখন কোনো একটা element access করতে চাই তার index এর মাধ্যমে তখন কিন্তু আমরা সরাসরি ওই element টাকে access করতে পারি এবং সেটা একটি element হয় যার জন্যই এটা Big O(1) )

• forEach - Big O(n)

  ( এটায় Big O(n) কারণ একটি forEach এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

• map - Big O(n)

  ( এটায় Big O(n) কারণ একটি map এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

• filter - Big O(n)

  ( এটায় Big O(n) কারণ একটি filter এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

• reduce - Big O(n)

  ( এটায় Big O(n) কারণ একটি reduce এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

Searching Algorithms

Linear Search

\> Lineasr Search বিষয়টি হচ্ছে কোনো একটা স্পেসিফিক জায়গা থেকে কোনো একটা জিনিস খুজে দিবে এবং খুজে দেয়ার পর সেখান থেকে চলে আসবে। তার মানে হচ্ছে আমরা বলে দিবো যে এই জায়গা থেকে আমাকে তুমি এই জিনিসটা এনে দাও linear search বিষয়টি হচ্ছে এইরকম।

Binary Search

\> binary search আমাদের টাইম কমপ্লেক্সিটি অনেক কমিয়ে দেয় এবং আমরা যে এলিমেন্ট খুজতে চাচ্ছি সেটা খুব সহজে বের করতে পারি। binary search করতে হলে আমাদের আগে আমাদের যে array টি থাকবে সেটাকে ascending order এ সাজাতে হবে এবং পরে সেটার উপর সার্চ করতে পারবো।

তাহলে চলেন নিচের ইমেজের মাধ্যমে আরো ভালোভাবে বুঝার চেষ্টা করি।

binary search এ আমরা তিনটি পয়েন্ট করি প্রথমে এবং সেই পয়েন্ট অনুসারে আমাদের যেই এলিমেন্ট খুজছি সেটা পাবো।

পয়েন্ট গুলো হচ্ছে,

1. Start Point

2. Middle Point

3. End Point

উপরের তিনটি পয়েন্টের মাধ্যমে আমরা খুব কম সময়ের মধ্যে আমদের যেই এলিমেন্ট খুজছি সেটা খুজে পাবো।

এখানে প্রসেসটি হচ্ছে এইরকম, আমরা প্রথমে সিলেক্ট করবো যে আমাদের start point কোনটি তারপর সিলেক্ট করবো আমাদের middle point কোনটি এবং শেষে সিলেক্ট করবো আমাদের end point কোনটি। এইগুলো সিলেক্ট হয়ে গেলে আমরা কন্ডিশন এর মাধ্যমে খুজে দেখবো যে আমাদের কাংক্ষিত এলিমেন্ট কি middle এর চেয়ে বড় নাকি ছোট ? যদি বড় হয় তাহলে আমরা সেই middle এলিমেন্ট এর পরের সব এলিমেন্ট বাদ দিয়ে দিবো কারণ আমাদের array টি তো ascending order এ সাজানো তাই না ? এবং যেহেতু আমাদের কাংক্ষিত এলিমেন্টটি middle এলিমেন্ট এর চেয়ে ছোট তাই আমরা middle এর আগের সব এলিমেন্ট এর উপর এখন search চালাবো এবং আমরা আমাদের start, middle, end point গুলো পরিবর্তন করে ফেলবো এভাবে যে আমাদের আগের middle point যেটা ছিলো সেটা হবে এখন end point এবং যেহেতু আমরা শেষের গুলো বাদ দিয়ে প্রথম দিকের এলিমেন্ট গুলোর উপর search করছি তাই আমদের আর start point পরিবর্তন করতে হবে না তাই middle point and end point পরিবর্তন করবো। এবং ওইখানে দেখবো যে এখন যেটা middle এলিমেন্ট আছে সেটা কি আমাদের কাংক্ষিত এলিমেন্ট এর চেয়ে ছোট নাকি বড় ছোট হলে তো আগের মতই পরিবর্তন করবো আর বড় হলে ও এবং যদি মিলে যায় তাহলে তো আমাদের output পেয়ে যাচ্ছি ( so now you can chill মজা করলাম )।

মুলত এইভাবেই binary search করা হয়। আর picture তো যুক্ত করে দিলামই যাতে আপনারা নিজে আর ভালো বুঝতে পারেন আমার বুঝানোর চেয়ে।

Sorting Algorithms

\> sorting slgorithms হচ্ছে কোনো একটা array কে ascending order এ কিংবা descending order এ সাজানোর জন্য ( ছোট থেকে বড় কিংবা বড় থেকে ছোট )। আমরা এই sorting algorithms এর মধ্যে অনেকগুলো algorithms পাই জেগুলো ব্যবহার করে খুব সহজে যেকোনো array sort করতে পারবো। নিচে কিছু দেয়া হলো,

Bubble Sort

\> bubble sort এর মাধ্যমে আমরা একটি array এর ২টি value নিয়ে নিয়ে তাদের মধ্যে compare করে দেখবো যে প্রথম value এর চেয়ে দ্বিতীয় value বড় নাকি ছোট যদি বড় হয় তাহলে আমরা swape করবো value গুলোকে, যেমন আমাদের প্রথম value বড় হলো দ্বিতীয় value এর চেয়ে তাহলে তো আমরা বুঝতে পারছি যে আমাদের ডান পাশের value টি হচ্ছে ছোট value এবং তাকে বাম পাশে আনতে হবে এবং বাম পাশের value কে ডান পাশে দিতে হবে। এভাবেই চেক করে করে আমরা bubble sorting করবো। এবং আরেকটা কথা হচ্ছে আমরা যখন সর্বশেষ লাস্ট বড় এলিমেন্ট পেয়ে যাব তখন দ্বিতীয় বার আর ওই লাস্ট এলিমেন্টকে বাম পাশের এলিমেন্ট দ্বারা চেক করবো না এবং এভাবেই চেকিং হবে।

নিচে কয়েকটি স্টেপের মাধ্যমে আর ক্লিয়ার করার চেষ্টা করেছি

আমি একটা ওয়েবসাইটের লিংক দিচ্ছি যেটাতে গেলে আপনি একটি ভিডিওর মাধ্যমে আরো ভাবে বুঝতে পারবেন যে operation টি হচ্ছে কেমনে।

https://visualgo.net/en/sorting

Selection Sort

\> Selection Sort বিষয়টি হচ্ছে একদম bubble sort এর মতই শুধু পরিবর্তনটি হচ্ছে আমরা bubble sorting এ তিনটি পয়েন্ট ধরতাম এবং সেগুলো দিয়ে array টি sort করতাম, কিন্তু selection sorting এ আমরা শুধুমাত্র একটি পয়েন্ট ধরবো যেটা হচ্ছে একটা lowest number এবং আমরা চেক করবো যে আমাদের lowest number কি তার পাশের number এর চেয়ে বড় ? যদি বড় হয় তাহলে তো আমাদের পাশের number টিকে lowest number এর ইনডেক্সে আনতে হবে কেননা ওই পাশের number টাই তো ছোট number এবং সেটা lowest number এর জায়গায় আসলে তবেই তো sorting টি হবে ছোট থেকে বড় হয়ে। এবং সংখ্যাটিকে আনার জন্য তো আমাদের swape করতে হবে তাই না ? আমরা swape করবো টিক যেভাবে bubble sort এ swape করেছিলাম ঠিক ওইভাবে।

আপনাদের বুঝার জন্য নিচে picture যুক্ত করেছি এবং একটি video ও যুক্ত করে দিয়েছি যাতে আপানারা খুব সহজে বিষয়টি বুঝতে পারেন।

video link -https://visualgo.net/en/sorting

Insertion Sort

\> Insertion Sort ঠিক selection sort এর মতই কিন্তু এখানে পরিবর্তনটি হচ্ছে, আমরা selection sorting এ বাম পাশের number এর সাথে ডান পাশের number এর ছোট এবং বড় কি না সেটা চেক করতাম। কিন্তু insertion sorting এ আমরা একই ভাবে ডান পাশের টার সাথে ছোট বড় চেক করবো কিন্তু যদি ডান পাশের number টি বাম পাশের number এত ছোট হয় যে সেটাকে আমার আর ২ ইনডেক্স সামনে আনার প্রয়োজন হচ্ছে তখন insertion sort এ backword cheking করা হয় এবং ওই number এর সঠিক পজিশনে পৌঁচে দেওয়া হয়। এবং insetion sorting এ আমরা এইভাবে চেকিং করতে করতে সামনের দিকে এগুতে থাকি আর এইরকম পরিস্তিতির সম্মুখীন হলে backword checking এর মাধ্যমে ওই number টির সঠিক পজিশনে নেয়া হয়।

আপনাদের বুঝার জন্য নিচে picture যুক্ত করেছি এবং একটি video ও যুক্ত করে দিয়েছি যাতে আপানারা খুব সহজে বিষয়টি বুঝতে পারেন।

video link -https://visualgo.net/en/sorting

Data Structure

\> Data Structure হচ্ছে একটি ওয়েবসাইটে আমাদের যত প্রয়োজনীয় ডাটা আছে সেগুলোকে খুব সুন্দর ভাবে সাজিয়ে রাখার মাধ্যম। ডাটা গুলো সুন্দর করে সাজিয়ে রাখলে পরবর্তীতে যখন আমি ওই ডাটাটি খুজতে যাবো অথবা ডাটাটি আপডেট করতে যাবো তখন আমার অন্য কোথাও খুজতে হবে না কারণ আমি জানি যে আমি এই ফাইলের মধ্যে ডাটাটি রেখেছি এবং তখন সরাসরি ওই ফাইলে যাবো এবং ডাটাটি নিয়ে আসতে পারবো। আর এটাই হচ্ছে data structure.

Stack

\> stack এর একটি প্রিন্সিপাল রয়েছে এবং সেটা হচ্ছে (LIFO).

• L = Last

• I = In

• F = First

• O = Out

এক কথায়, Last In First Out বলা হয়েছে এখানে। যেটার মানে হচ্ছে যে সবার শেষে আসবে সে সবার প্রথমে বেরিয়ে যাবে এবং যে সবার প্রথমে আসবে সে সবার শেষে বেরিয়ে যাবে।

ওকে, জিনিসটা আর ক্লিয়ার করি একটি ইমেজের মাধ্যমে.........

এখানে ইমেজটি লক্ষ করুন, আমি যখন প্লেট রাখছিলাম তখন একটার উপর একটা এভাবে রাখছিলাম এবং আমি সব প্লেট রেখে দিয়েছি। পরে আমার আম্মু বললো যে উনাকে একটা প্লেট এনে দিতে, তো আমি গিয়ে উপরে যে প্লেটটি আছে সেটি নিয়ে এসে উনাকে দিবো তাই না ? হে, কারণ আমি চাইবো না যে নিচ থেকে একটা প্লেট এনে দেই কারণ সে ক্ষেত্রে পুরো প্লেটের স্তুবটি ভেঙ্গে যেতে পারে এবং না ভাঙ্গলে ও এতো কষ্ট নিয়ে আসবো না আমি। তাহলে এখানে ঘটনা কি হলো ? আমি যেই প্লেটটি সবার প্রথমে রেখেছিলাম সেটা নিচে রয়ে গেলো এবং যেই প্লেটটি সবার শেষে রেখেছিলাম সেটা উপরে রয়ে গেলো এবং আমি যখন প্লেট নিতে আসছি তখন ওই উপরের প্লেটটি নিয়ে গেছি। তাহলে আমাদের LIFO এর প্রমাণ হয়ে গেলো।

Queue

\> Queue এর একটি প্রিন্সিপাল রয়েছে এবং সেটা হচ্ছে (FIFO).

• F = First

• I = In

• F = First

• O = Out

এক কথায়, First In First Out বলা হয়েছে এখানে। যেটার মানে হচ্ছে যে প্রথমে আসবে সে প্রথমে বেরিয়ে যাবে এবং যে শেষে আসবে সে শেষে বেরিয়ে যাবে।

এখানে ইমেজটি লক্ষ করুন, ইমেজে ২টি পার্ট রয়েছে একটা হচ্ছে front এবং আরেকটা হচ্ছে back. তো আমরা যে ডাটা গুলো insert(যুক্ত করবো) সেগুলো back পার্ট দিয়ে যুক্ত হবে এবং যখন আমরা সেই ডাটাটি get(পেতে চাইবো) তখন front পার্ট দিয়ে বেরিয়ে আসবে। এবং অবশ্যই সেক্ষেত্রে আমরা সে ডাটা আগে যুক্ত করবো সেটা আগে বেরিয়ে আসবে এবং সেটা পরে যুক্ত করবো সেটা পরে বেরিয়ে আসবে। তাহলে আমাদের FIFO এর প্রমাণ হয়ে গেলো।

Linked List

What is Linked List?

\> ডেটা স্টোর করার জন্য অ্যারের মত আরেকটি ডেটা স্ট্যাকচার হচ্ছে Linked List। এটি স্ট্র্যাকচার অনুযায়ী ডাটা স্টোর করে, এবং রান টাইমে নতুন স্পেসের দরকার হলে অটোমেটিকেলি তা তৈরি করে নিতে পারে। এটি হচ্ছে ডাইনামিক ডেটা স্ট্রাকচার।

এটি অ্যারের মতই, তবে অ্যারেতে আমাদের কতটুকু মেমরি দরকার, প্রথমেই বলে দিতে হয়। কিন্তু লিঙ্কড লিস্টে প্রয়োজন অনুযায়ী মেমরি বাড়ানো বা কমিয়ে নেওয়া যায়। আরো দুইটা সুবিধে হচ্ছে, লিঙ্কড লিস্টের মাঝখান থেকে এর যে কোন আইটেম রিমুভ করা যায় বা মাঝখানে নতুন আইটেম যুক্ত করা যায়। আর ইনিশালি কোন সাইজ ডিক্লেয়ার করে দিতে হয় না।

অসুবিধেও রয়েছে। অ্যারে রেন্ডম এক্সেস করা যায়, কিন্তু লিঙ্কড লিস্টে রেডম এক্সেস করা যায় না।

লিঙ্কড লিস্ট হচ্ছে ডাইন্যামিক্যালই এলোকেটেড নোড। প্রত্যেকটা নোডের একটা ভ্যালু এবং একটা পয়েন্টার থাকে। পয়েন্টার এর পরবর্তি নোড বা লিঙ্কড লিস্টের পরবর্তি মেম্বারকে পয়েন্ট করে। এটা ট্রেনের মত। প্রথম মেম্বার হচ্ছে ট্রেনের ইঞ্জিন। এবং এরপরবর্তী বগিটি ইঞ্জিনের সাথে কানেকটেড থাকে, যা পয়েন্টার। পরের বগিটি এর পরের বগিটির সাথে কানেকটেড থাকে। যদি শেষে কোন বগি না থাকে, তখন আমরা বলি ট্রেনের শেষ। একই ভাবে লিঙ্কড লিস্টের পয়েন্টার যদি শূন্য হয়, তাহলে আমরা বলি এর পর আর কোন মেম্বার নেই। লিঙ্কড লিস্টে প্রথম নোড অনেক গুরুত্বপূর্ন, কারণ এটাতে পরবর্তী মেম্বারের পয়েন্টার থাকে। যদি প্রথম মেম্বার কোন ক্রমে রিমুভ হয়ে যায়, তাহলে পুরো লিঙ্কড লিস্টিই আর খুঁজে পাওয়া যাবে না। ট্রেনের ইঞ্জিন ছাড়া অন্য বগি গুলো যেমন কোন কাজে আসে না।

নিচের ছবিটি লক্ষ করুন,

এটি হচ্ছে লিঙ্কড লিস্টের একটি নোড। নোডের দুইটা অংশ, একটা হচ্ছে ডেটা। আরেকটা হচ্ছে এড্রেস। এমন অনেক গুলো নোড নিয়েই লিঙ্কড লিস্ট তৈরি। প্রথম নোডের Address দ্বিতীয় নোডের এড্রেস পয়েন্ট করা থাকে। নিচের ছবিটির মতঃ

এভাবে যত ইচ্ছে তত গুলো নোড যুক্ত করা যায়।

ট্রেনের এক একটা আলাদা ব্লককে আমরা বলি বগি, লিঙ্কড লিস্টে আমরা বলব নোড।

Linked List দুই ধরণের। নিচে দেওয়া হলঃ

• Singly Linked List

• Doubly Linked List

Singly Linked List

\> Singly Linked List এ আমরা head এবং tail নামক ২টি জিনিস পাই, যেটা দিয়ে আমরা বুঝতে পারবো যে আমাদের কোন এলিমেন্ট head এবং কোন এলিমেন্ট tail আর head এর মানে হচ্ছে সবার প্রথম সংখ্যা এবং tail এর মানে হচ্ছে সবার শেষের সংখ্যা। এরপর Singly Linked List এ আমরা next নামে ও একটি জিনিস পাই যেটা দ্বারা আমরা জানতে পারি যে আমাদের current এলিমেন্টের পরে কোন এলিমেন্ট রয়েছে। আচ্ছা বুঝতে না পারলে সমস্যা নয়, নিচের ছবিটি দেখেন এবং ওই ছবি থেকে আমরা আরো বিস্তারিত আলোচনা করবো নিচে।

উপরের ছবিটি লক্ষ করলে দেখবেন যে একদম প্রথমে head রয়েছে এবং একদম শেষে tail রয়েছে এবং মাঝখানে length রয়েছে। এবং নিচের যে arrow চিহ্ন দিয়ে next next দেখানো হয়েছে ওটা হচ্ছে এড্রেস এবং সেখানে আমরা দেখতে পারবো যে আমাদের এই এলিমেন্টের পরে next কোন এলিমেন্ট রয়েছে। আর এভাবে আমাদের Singly Linked List চলতে থাকবে এবং সবার শেষে মানে tail এ যে থাকবে তার কোনো next value থাকবে না মানে ওই এলিমেন্টের next value null থাকবে।

Singly Linked List - delete last node using POP method

উপরের ছবিটিতে দেখা যাচ্ছে যে একটি head এবং একটি tail রয়েছে ( আগে যেভাবে বলেছিলাম ) তারপর আমাদের node গুলো রয়েছে এবং বলেছিলাম যে প্রত্যেকটি node এর সাথে next নামে একটা প্রপার্টি থাকে যার মাধ্যমে আমরা জানতে পারি যে আমাদের এই node এর পরবর্তী node কোনটি অথবা তার value কত? তাহলে এইবার আমরা চাচ্ছি যে আমাদের এই singly linked list থেকে সবার শেষে যে এলিমেন্টটি থাকবে থাকে ডিলিট করবো, তাহলে আপনারা বলতে পারেন যে আমরা তো সেটি পেয়ে যাচ্ছি যদি আমরা tail কে ধরি তাহলেই। না, Linked List এ এইভাবে করা যায় না। কারণ Linked List এ আমরা একটি এলিমেন্ট থেকে পরের এলিমেন্টে যেতে হলে পয়েন্টার ব্যবহার করে যেতে হয় যেটা আমরা Linked List এর সব Node এর মধ্যে পেয়ে থাকি ( next যেটা ওইটাই )। তাহলে আমরা যদি POP মেথডের সাহায্যে কোনো node ডিলিট করতে চাই তাহলে, উপরের Diagram এ দেয়া আছে সেভাবে ফলো করবো। প্রথমে আমাদের প্রথম যে node আছে সেটাকে currentNode নামে একটি variable এ রাখবো এবং আমরা চেক করবো যে আমাদের এই currentNode এর ভিতরে next নামে যে প্রপার্টি রয়েছে সেটা কি আমাদের পুরো Linked List এর যে Tail রয়েছে সেটার সমান? যদি সমান হয় তাহলে তো আমরা লাস্ট node টি পেয়ে গেলাম আর যদি সমান না হয় তাহলে আমরা ওই currentNode এর nextNode যেটা আছে ওইটাকে currentNode বানিয়ে দিবো এবং আবার সেইম প্রসেসে চেক করবো যে এই currentNode এর nextNode কি আমাদের tail এর সমান? এভাবে চেক করে করে আমরা পুরো node দেখবো এবং যেখানে গিয়ে আমরা tail এর সমান পাবো ( অর্থাৎ, if(next === tail) সত্যি হলে ) আমরা ওই node টাকে delete করে দিবো এবং আমাদের tail কে নিয়ে আসবো আমরা যে currentNode পেয়েছি ওইটায়, মানে এখন tail হচ্ছে ওই currentNode। এবং সর্বশেষ যখন আমাদের list এ কোনো node থাকবে না তখন আমরা আমাদের head এবং tail করে দিবো null কে ( মানে শুরুতে যেভাবে ছিলো সেভাবে )।

Singly Linked List - delete first node using SHIFT method

\> এবার আমরা চাচ্ছি যে আমাদের লিস্টের মধ্যে থাকা সব node থেকে সবার প্রথমে যেটা থাকবে সেটাকে delete করে দিবো যখন Shift() মেথডটি call করবো তখন। এবং এই কাজটি অনেক সহজ। আমরা প্রথমে চেক করে নিবো যে আমাদের লিস্টটি কি একেবারে খালি নাকি যদি খালি থাকে তাহলে আমরা null রিটার্ন করবো নাহলে আমাদের delete এর করবো। তো delete করার জন্য আমাদের প্রথমে একটি variable নিতে আমাদের যে head রয়েছে সেটাকে currentNode নামক একটি variable এ রাখবো। তারপর আমরা আমাদের লিস্টের যে tail রয়েছে তার সমান currentNode এর next বসিয়ে দিবো ( this.tail = currentNode.next এভাবে )। তাহলেই তো আমাদের delete করা সম্পূর্ণ। এরপর আমরা আমাদের লিস্টের length কমিয়ে দিবো, কারণ একটি node delete হয়ে গেলে তো আমাদের একটি length কমাতে হবে তাই। এরপর আমরা আরেকটা চেক করবো যে যদি আমাদের length === 0 হয় তাহলে tail যেন null হয়ে যায়। কারণ head null হয়ে যাবে shift() call করার মাধ্যমে কিন্তু দেখা যাবে যে আমাদের tail এ value রয়ে গেছে তার কারণে আমরা এটা করবো যে যখন length 0 হয়ে যাবে তখন tail এর value null হয়ে যাবে এবং tail এর next ও null হয়ে যাবে। এককথায় সব কিছু null থাকবে যদি length 0 হয়ে যায়।

reference এর জন্য নিচে কোড দিয়ে দিলাম কিভাবে shift method implement করা যায়।

// shift method
shift() {
    // চেক করা হচ্ছে যে আমাদের লিস্ট খালি কি না।
    if (!this.isEmpty()) {
      // currentNode নামক একটি variable এ আমাদের লিস্টের head কে রাখা হচ্ছে।
      let currentNode = this.head;

      // এবার delete করা হচ্ছে জাস্ট আমাদের লিস্টের head কে currentNode এর next বানিয়ে দেওয়া হচ্ছে।
      this.head = currentNode.next;

      // এবার লিস্টের length কমানো হচ্ছে।
      this.length--;

      // চেক করা হচ্ছে যে যদি লিস্টের length 0 হয় তাহলে tail যেনো null হয়ে যায়।
      if (this.length === 0) {
        this.tail = null;
      }

      // সবার শেষে currentNode return করা হচ্ছে।
      return currentNode;
    }
  }

Singly Linked List - Add the node in the first position of the list using the UNSHIFT method

\> প্রথমে তো আমরা আমাদের লিস্টে node যুক্ত করেছিলাম লাস্টের দিক দিয়ে যেভাবে কোনো array তে push() method ব্যবহার করে করতাম। কিন্তু এখন আমরা চাচ্ছি যে যখন কোনো node যুক্ত করবো তখন সেই node যেনো আমাদের লিস্টের প্রথম দিকে যুক্ত হয় মানে array এর unshift() method যেভাবে কাজ করে ওইভাবেই। এটা করার জন্য বেশি কোনো কাজ করতে হবে না। আমরা যখন কোনো node যুক্ত করবো তখন ওই node কে আমাদের লিস্টের head বানিয়ে দিবো এবং নতুন যে node তৈরি করেছি সেই node এর next বানিয়ে দিবো আমাদের আগের head যেটা ছিলো ওইটাকে তাহলেই আমাদের node যুক্ত করা হয়ে যাবে।

বিষয়টি হয়তো ক্লিয়ার হন নি। তাই নিচে কোড দেওয়া হলো এবং কমেন্টের মাধ্যমে বুঝানো হলো কোন লাইন কি কাজে ব্যবহার হচ্ছে।

// unshift method
unshift(value) {
    // এখানে নতুন node তৈরি করা হচ্ছে। যখন unshift method call করা হবে তখন আপনি একটি value দিবেন আর ওই value দিয়েই এই নতুন node তৈরি করা হচ্ছে।
    let newNode = {
      head: value,
      next: null,
    };

    // চেক করা হচ্ছে আমাদের লিস্ট কি empty। যদি empty হয় তাহলে if এর কাজ করবে না হলে else এর কাজ করবে।
    if (this.isEmpty()) {
      // এখন আমাদের লিস্টের head যেটা রয়েছে সেটার value হিসেবে আমাদের নতুন node কে দেয়া হলো
      this.head = newNode;

      // এখন আমাদের লিস্টের tail যেটা রয়েছে সেটার value হিসেবে আমাদের নতুন node কে দেয়া হলো
      this.tail = newNode;
    } else {
      // আমাদের নতুন node যখন তৈরি করেছিলাম তখন নতুন node এর next কে null রেখেছিলাম তাই এখন ওই নতুন node এর next এর value হিসেবে আমাদের আগের head কে দিয়ে দিচ্ছি।
      newNode.next = this.head;

      // এখানে আমাদের লিস্টের head এর জায়গায় আমাদের নতুন node কে বসিয়ে দিচ্ছি।
      this.head = newNode;

      // এবার একটি node যুক্ত হলে তো আমাদের লিস্টের length ও বৃদ্ধি করতে হবে সেটাই এখানে করা হচ্ছে।
      this.length++;
    }
  }

Doubly Linked List

\> উপরের ছবিটি লক্ষ করুন, Doubly linked list এর সবকিছু সেইম singly linked list এর মতো, শুধু পরিবর্তনটি হচ্ছে singly linked list এ আমরা previous নামে কোনো জিনিস পেতাম না কিন্তু Doubly linked list এ আমরা previous নামে একটা property পাচ্ছি যেটার মাধ্যমে আমাদের currentNode এর আগের node কোনটি সেটা জানতে পারবো। তাছাড়া বাকি সব singly linked list এর মতো।

Doubly Linked List - Add the node in the last position of the list using the PUSH method

\> Singly Linked List এ আমরা যেভাবে push method ইমপ্লেমেন্ট করে লিস্টের শেষের দিকে node যুক্ত করেছিলাম ঠিক সেইভাবেই Doubly Linked List এ করতে পারবো, শুধু একটি জিনিস বাড়বে আরা সেটা হচ্ছে previous point. উপরে বলা হয়েছে যে Doubly Linked List এ মোট তিনটি প্রপার্টি পাবো (value, next, prev)। সেইম ভাবে আমাদের head এবং tail থাকবে লিস্টে এবং length থাকবে। প্রথমে আমরা চেক করে নিবো যে আমাদের লিস্টে কোনো node আছে কি না, যদি না থাকে তাহলে তো আমরা যে node যুক্ত করবো সেটা হবে head এবং সেটাই হবে tail আর প্রথম node এর next value থাকবে null এবং prev value থাকবে null। তারপর যদি আমাদের লিস্টে আগে থেকে একটি node যুক্ত করা থাকে তাহলে আমরা যখন আরেকটি নতুন node যুক্ত করবো তখন তো ওই node এর next এবং prev value অবশ্যই থাকবে। আর সেটা আমরা এভাবে করবো যে আমাদের বর্তমান যে tail রয়েছে সেটার next এর value সমান করে দিবো আমাদের নতুন যে node যুক্ত হতে চাচ্ছে সেটাকে এবং আমাদের নতুন node এর prev value সেট করে দিবো আমাদের যে tail রয়েছে সেটাকে এবং অবশেষে আমাদের tail এর value সেট করে দিবো আমাদের নতুন যে node যুক্ত হতে চাচ্ছে সেটাকে, ব্যাস আমাদের কাজ হয়ে গেছে সবার শেষে আমরা আমাদের লিস্টের length বাড়িয়ে দিবো।

নিচের কোডের মাধ্যমে আরো ভালোভাবে Doubly Linked List এ Push method ইমপ্লিমেন্ট করা হলো।

// push method implement

// একটা টেম্পলেট তৈরি করে নিলাম যাতে আলাদা করে আবার সব প্রপার্টি গুলো লিখতে না হয়।
class NodeTemplete {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

// এটা হচ্ছে আমাদের মেইন Doubly Linked List ক্লাস।
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // চেক করে নিচ্ছি যে আমাদের লিস্ট কি empty নাকি। এটা আমাদের true or false রিটার্ন করবে।
  isEmpty() {
    return this.length === 0;
  }

  // এইটা হচ্ছে আমাদের push method
  push(value) {
    // এখানে আমরা যে value পাচ্ছি তা দিয়ে নতুন একটি node তৈরি করে নিচ্ছি। আমরা আগে যে টেম্পলেট তৈরি করেছিলাম সেটা এখানে call করলাম এবং আমাদের value টি দিয়ে দিলাম।
    let newNode = new NodeTemplete(value);

    // আবার চেক করা হচ্ছে, যদি আমাদের head না থাকে তাহলে if এর কাজ করবে ( head null থাকলে আরকি ) আর যদি head এ কোনো node থেকে থাকে তাহলে else এর কাজ করবে।
    if (!this.head) {
      // এখানে আমাদের head করে দিলাম নতুন যে node সেটা।
      this.head = newNode;

      // এখানে আমাদের tail করে দিলাম নতুন যে node সেটা।
      this.tail = newNode;
    } else {
      // এখানে আমাদের যে tail রয়েছে সেটার next প্রপার্টির value করে দিলাম আমাদের নতুন node কে।
      this.tail.next = newNode;

      // এখানে আমাদের যে নতুন node রয়েছে সেটার previous value সেট করে দিলাম আমাদের আগের যে tail ছিলো সেটাকে।
      newNode.prev = this.tail;

      // তারপর যেহেতু আমরা নতুন একটি node শেষের দিকে যুক্ত করলাম, তাই আমাদের লিস্টের tail করে দিলাম আমাদের নতুন node কে।
      this.tail = newNode;
    }

    // এখন একটি node যুক্ত করলে তো আমাদের লিস্টের length ও বাড়াতে হবে সেটা এখানে করলাম।
    this.length++;
  }
}

let test = new DoublyLinkedList();
test.push(5);
test.push(10);

console.log(test);

Doubly Linked List - Delete the node in the last position of the list using the POP method

\> Doubly Linked List এ লাস্টের দিক থেকে কোনো node ডিলিট করা সেইম Singly Linked List এর মতোই শুধু পার্থক্য হচ্ছে Doubly Linked List এ prev যে আরেকটি value থাকে সেটা। ওকে, আমরা Singly Linked List এ লাস্টের দিকের node ডিলিট করার জন্য চেক করতাম যে আমাদের currentNode ( currentNode নামে একটি variable নিতাম এবং এর value সেট করে দিতাম head কে ) কি আমাদের tail এর সমান, যদি সমান হয় তাহলে আমরা currentNode টিকে আমাদের tail বানিয়ে দিতাম এবং currentNode এর next করে দিতাম null। কিন্তু Doubly Linked List এ এর কিছুটা ব্যতিক্রম। আমরা Doubly Linked List এভাবে করবো... প্রথমে চেক করে নিবো আমাদের যদি কোনো node না থাকে তাহলে আমরা জাস্ট null রিটার্ন করে দিবো। আর যদি আমাদের শুধুমাত্র একটি node থেকে থাকে তাহলে আমরা আমাদের লিস্টের head এবং tail কে null করে দিবো ( মানে ওই node টি ডিলিট হয়ে গেছে )। এবার আসি মুল ডিলিটেশনে, আমাদের লিস্টের tail যেটা আছে সেটা প্রথমে আমরা একটি variable এ রাখবো। তারপর আমাদের লিস্টের tail করে দিবো যে বর্তমানে tail আছে তার prev কে ( মানে বর্তমান tail এর previous value যেটা আছে ওইটাকে )। এবার আমরা তো সব লাস্টের node টি ডিলিট করতে চাচ্ছি এবং আমরা জানি যে আমাদের যে tail রয়েছে তার next value হচ্ছে null তাই আমরা যেহেতু এখন নতুন tail তৈরি করে নিয়েছি তাই ওই tail এর next value করে দিবো null। কিন্তু এখনো একটি কাজ বাকি আছে... আমাদের আগের যে tail ছিলো ( মানে ডিলিট করার আগে ) সেটার কিন্তু একটি prev node ছিলো কিন্তু আমরা তো এখন ওই tail ডিলিট করে দিয়েছি তাই আমাদের ওই tail এর prev কে ও null করে দিতে হবে। ব্যাস আমাদের কাজ হয়ে গেছে। এবার জাস্ট লিস্টের length কমিয়ে দিলেই হয়ে যায়।

ওকে, পেরা নেয়ার প্রয়োজন নাই নিচে কোড দিচ্ছি এবং সাথে তো কমেন্ট থাকছেই।

// pop method implement
pop() {
    // চেক করে নিচ্ছি লিস্ট কি পুরো খালি।
    if (!this.head) {
      return null;
    }

    // নতুন একটি variable এ আমাদের tail কে রাখলাম।
    let popNode = this.tail;

    // এবার চেক করে নিচ্ছি যদি আমাদের লিস্টে একটি node থাকে তাহলে আমরা if এর কাজ করবো নাহলে else এর কাজ।
    if (this.head === 1) {
      // head কে null করে দিচ্ছি।
      this.head = null;

      // tail কে null করে দিচ্ছি।
      this.tail = null;
    } else {

      // বর্তমানে আমাদের লিস্টের যে tail হবে সে হচ্ছে আমাদের লিস্টের আগে যে tail ছিলো তার previous এ থাকা node।
      this.tail = popNode.prev;

      // এবং আমাদের লিস্টের আগের tail এর next এর value করে দিচ্ছি null।
      popNode.next = null;

      // এবং আমাদের লিস্টের আগের tail এ থাকা prev কে ও null করে দিচ্ছি।
      popNode.prev = null;
    }

    // লিস্টের length কমাচ্ছি।
    this.length--;

    // সবার শেষে আমাদের নতুন যে tail তৈরি করলাম সেটা রিটার্ন করে দিচ্ছি।
    return popNode;
  }

Doubly Linked List - Add the node in the first position of the list using the UNSHIFT method

\> সংক্ষেপে বুঝার চেষ্টা করি আমরা, যেহেতু আমাদের Doubly linked list এ previous node রয়েছে তাই এটি Singly linke list থেকে ভিন্ন এবং এটিতে Push, Pop, Unshift, Shift এগুলো ইমপ্লিমেন্ট করাও একটু ভিন্ন Singly linked list থেকে। ওকে কাজের কথায় আসি, আমরা এখন Unshift এর মাধ্যমে লিস্টের প্রথম দিকে node যুক্ত করতে চাচ্ছি তাই আমাদের এটি ইমপ্লিমেন্ট করতে হবে। আমরা এটা করবো যে... প্রথমে তো চেক করে নিবো যে আমাদের লিস্টে কোনো node আছে কি না এবং আমাদের নতুন node কে একটি variable এ স্টোর করে রাখবো। তারপর আমাদের লিস্টের যে head রয়েছে তার যে prev node রয়েছে তাকে আমাদের নতুন node করে দিবো ( শুরুতে prev কিন্তু ছিলো null )। এরপর আমাদের নতুন node এর next node করে দিবো আমাদের যে head রয়েছে থাকে এবং আমরা যখন নতুন node লিস্টের প্রথমে যুক্ত করতে চাচ্ছি সেহেতু আমরা যে node যুক্ত করবো সেটিই তো আমাদের head হবে তাই না ? এজন্যই এবার আমরা আমাদের লিস্টের head করে দিবো আমাদের যে নতুন node তাকে ব্যাস আমাদের node যুক্ত করা হয়ে গেছে।

বুঝেননি! কোনো ব্যাপার না নিচে কোড দেওয়া হলো এবং সাথে তো অবশ্যই কমেন্ট করা আছে।

// unshift method implement

// এটা একটি টেম্পলেট নতুন node এর জন্য।
class NodeTemplete {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

unshift(value) {

    // এখানে আমাদের নতুন node একটি variable এর মধ্যে রাখছি এবং উপরে যে টেম্পলেট তৈরি করেছিলাম সেটা call করে দিয়েছি।
    let newNode = new NodeTemplete(value);

    // চেক করছি যদি কোনো node না থাকে তাহলে if কাজ করবে থাকলে else কাজ করবে।
    if (!this.head) {

      // লিস্টের head হয়ে যাবে নতুন node
      this.head = newNode;

      // লিস্টের tail হয়ে যাবে নতুন node
      this.tail = newNode;
    } else {

      // আমাদের লিস্টের যে head রয়েছে তার prev তো null থাকবে তাই না, তো আমরা সেটাকে করে দিচ্ছি নতুন node। কারণ আমরা তো লিস্টের প্রথমে node যুক্ত করতে চাচ্ছি।
      this.head.prev = newNode;

      // আমাদের নতুন যে node আছে সেটার next তো ইনিশিয়ালি null থাকে তো আমরা সেটাকে করে দিচ্ছি আমাদের লিস্টের যে head আছে সেটা।
      newNode.next = this.head;

      // সবার শেষে আমরা আমাদের head টা তো পরিবর্তন করতে হবে এবং সেটাই করছি head বানিয়ে দিচ্ছি আমাদের নতুন node কে।
      this.head = newNode;
    }

    // এবং ফাইনালি লিস্টের length বাড়িয়ে দিচ্ছি।
    this.length++;
  }

Doubly Linked List - Delete the node in the first position of the list using the SHIFT method

\> লিস্টের প্রথম থেকে node ডিলিট করার জন্য আমাদের প্রথমে ধরতে হবে head কে এবং সেটাকে একটি variable এর মধ্যে স্টোর করে রাখবো oldHead নামে ( কারণ আমরা যদি প্রথম থেকে একটি node ডিলিট করি তাহলে তো সেটি আমাদের head ই থাকবে আর head কে ডিলিট করে দিলে তো নতুন আরেকটি node কে head বানিয়ে দিতে হবে )। তারপর চেক করে নিবো যে আমাদের লিস্টে কোনো node আছে নাকি না থাকলে null রিটার্ন করে দিবো এবং যদি শুধু একটি node থাকে লিস্টে তাহলে সেটাকে ডিলিট করে head, tail কে null করে দিবো। এবার, আমরা তো প্রথম থেকে node ডিলিট করতে চাচ্ছি তাই আমাদের যে oldNode রয়েছে সেটার next কে করে দিবো আমাদের নতুন head এবং এটাকে যদি নতুন head করি তাহলে এটার তো অবশ্যই একটি prev node রয়েছে কিন্তু আমরা তো জানি যে head এর prev node null থাকে এবং tail এর next node null থাকে তাহলে তো এবার আমাদের এই node এর prev node null করে দিতে হবে। এবার আমাদের oldNode যেটা ছিলো ( মানে একদম শুরুর যে head ) তার তো একটি next node ছিলো যেটাকে আমরা এখন নতুন head তৈরি করেছি তাই আমাদের এবার ওই oldNode এর next node null করে দিতে হবে তাহলেই আমাদের ডিলিট সম্পূর্ণ হয়ে যাবে। এবং সবার শেষে তো length কমিয়ে দিতে হবে অবশ্য।

ওকে, না বুঝে থাকলে নিচে কোড দেওয়া হয়েছে এবং সাথে তো কমেন্ট আছেই।

// shift method implement
shift() {

    // চেক করা হচ্ছে যে আমাদের লিস্টে কোনো node আছে কি না।
    if (!this.head) {
      return null;
    }

    // oldNode নামে একটি variable এর মধ্যে আমদের বর্তমান head কে রাখা হচ্ছে।
    let oldHead = this.head;

    // চেক করা হচ্ছে আমাদের লিস্টে শুধু একটি node থাকলে if কাজ করবে না হলে else কাজ করবে।
    if (this.head === 1) {
      // head হয়ে যাবে null
      this.head = null;

      // tail হয়ে যাবে null
      this.tail = null;
    } else {

      // এখন আমাদের লিস্টের নতুন head যাবে আগের head এর next এ থাকা node
      this.head = oldHead.next;

      // আমাদের লিস্টের আগের head এর next node হয়ে যাবে null
      oldHead.next = null

      // এখন আমরা যে নতুন head তৈরি করেছি তার prev node হয়ে যাবে null
      this.head.prev = null;
    }

    // আমাদের লিস্টের length কমে যাবে।
    this.length--;

  }

Time complexity - Singly Linked List VS Doubly Linked List

Singly Linked List

• Push - O(1)

• Pop - O(n)

• Unshift - O(1)

• Shift - O(1)

• ShowAllNodeAsArray - O(n)

Doubly Linked List

• Push - O(1)

• Pop - O(1)

• Unshift - O(1)

• Shift - O(1)

Binary Tree

\> যে ট্রি এর নোডগুলোতে সর্বোচ্চ দুইটি child থাক্কে পার তাকে বাইনারি ট্রি বলা হয়। নোডগুলোতে লিঙ্কড লিস্টের মোট এর বা একাধিক ডেটা স্টোর করার ফিল্ড/ভেরিয়েবল থাকতে পারে। আর থাকবে এই নোডের left child এবং right child এর মেমরি এড্রেস। যার মাধ্যমে এদেরকে অ্যাক্সেস করা যায়।

Binary Tree হচ্ছে ৩ প্রকারঃ

1. Full Binary Tree

2. Complete Binary Tree

3. Perfect Binary Tree

Full Binary Tree

\> এমন একটা বাইনারি ট্রি যার নোডগুলোতে ০ থেকে ২ টি child থাকতে পারে। অর্থাৎ কোনও নোডে একটা child থাকলে সেটা full binary tree হবে না। একে proper binary tree, strictly binary tree বা plane binary tree বলা হয়।

Complete Binary Tree

\> যে বাইনারি ট্রি এর শেষ লেভেল বাদে বাকি সব লেভেল সম্পূর্ণ ভাবে child দ্বারা পূর্ণ তাকে Complete Binary Tree বলে। অর্থাৎ সবগুলো নোডেই দুটি করে child আছে এবং শেষের লেভেলের ক্ষেত্রে নোডগুলো fill up হতে হবে একদম বাম বাশ থেকে। বামের দিকের কোনো একটা নোডের জায়গা ফাঁকা রেখে ডান দিকে নোড যুক্ত করলে তাকে Complete Binary Tree বলা যাবে না।

Perfect Binary Tree

\> যেই বাইনারি ট্রি এর প্রত্যেকটি inteior node দুটি child থাকে এবং সকল leaf এর depth ও level একই হবে।

Binary Search Tree - Add Node

\> আমরা জানি যে আমাদের binary tree তে একটি root রয়েছে। এবং সেই root এর under এ left এবং right রয়েছে। আর binary tree এর left এ থাকা সব node কিন্তু ছোট হয়ে থাকে এবং right এ থাকা সব node বড় হয়ে থাকে। তাই আমরা যে নতুন node যুক্ত করতে চাচ্ছি যেটা বড় হলে right এ পাঠিয়ে দিবো আর ছোট হলে left এ পাঠিয়ে দিবো। এখন প্রথমে আমাদের চেক করতে হবে যে আমাদের tree তে আধো কোনো root আছে কি না কারণ শুরুর দিকে তো আমাদের কোনো root থাকবে না তাহলে আমাদের প্রথমে root তৈরি করতে হবে। এবং সেজন্যই আমরা চেক করবো যে আমাদের কোনো root আছে কি না যদি না থাকে তাহলে আমরা যে নতুন node যুক্ত করতে চাচ্ছি সেটাকে বানিয়ে দিবো root। আর যদি আমাদের tree তে root থেকে থাকে তাহলে আমরা চেক করবো যে আমরা যে নতুন node যুক্ত করতে চাচ্ছি সেটি কি আমাদের root এর চেয়ে বড় নাকি ছোট। যদি ছোট হয় তাহলে নতুন node কে পাঠিয়ে দিবো left এর দিকে আর যদি বড় হয় তাহলে নতুন node কে পাঠিয়ে দিবো right এর দিকে। এখন যখন নতুন node left অথবা right এ যাবে তখন ওইখানে ও তো left এবং right থাকবে। তাহলে আমরা যখন বুঝে যাবো যে আমাদের নতুন node আমাদের root এর চেয়ে বড় নাকি ছোট তখন তো left অথবা right এ পাঠাবো এবং যেদিকেই পাঠাই না কেনো ওইদিকে যাওয়ার আগে আবার চেক করবো যে অইখানে কোনো node আছে নাকি যদি না থাকে তাহলে সরাসরি ওইখানে আমাদের নতুন node বসিয়ে দিবো আর যদি থেকে থাকে তাহলে আমরা আমাদের আগের যে root ছিলো সেটাকে করে দিবো এখন এইখানে থাকা node কে এবং আবার চেক করবো যে এই root এর চেয়ে বড় নাকি ছোট আমাদের নতুন node টি এবং এভাবেই আমাদের node যুক্ত করার প্রসেস চলতে থাকবে এবং ঠিক সেইম ভাবেই right এর দিকে ও।

নিচে কোড দেওয়া হলো এবং সাথে কমেন্ট করে বুঝানো হলো কোন লাইন কি কাজ করছে।

// add node in binary tree

// এখানে একটি টেম্পলেট তৈরি করা হলো নতুন node এর জন্য যাতে পরবর্তীতে যেকোনো জায়গায় ব্যবহার করা যায়।
class Node {
  constructor(value) {
    this.leftChid = null;
    this.rightChild = null;
    this.value = value;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // add method
  addNode(value) {
    // নতুন node একটি variable এ রাখা হলো।
    let newNode = new Node(value);

    // চেক করা হলো যদি root null হয়ে থাকে তাহলে আমাদের root হয়ে যাবে নতুন যে node যুক্ত করতে চাচ্ছি সেটি। আর null না হলে else চলবে।
    if (this.root === null) {
      this.root = newNode;
    } else {
      // currentRoot variable এর মধ্যে আমাদের tree এর যে root রয়েছে তাকে রাখলাম।
      let currentRoot = this.root;

      // এখানে একটি বুলিয়ান value রাখলাম যাতে পরবর্তীতে প্রোগ্রাম রান ব্রেক করতে পারি।
      let added = false;

      // while loop চলবে যদি আমাদের added true না হয় এবং যদি currentRoot null না হয় তাহলে।
      while (!added && currentRoot) {
        // যদি আমাদের নতুন node আমাদের tree এর currentRoot এর value এর চেয়ে ছোট হয় তাহলে
        if (value < currentRoot.value) {
          // যদি আমাদের currentRoot এর left এ কোনো node না থাকে তাহলে
          if (currentRoot.leftChid === null) {
            // currentRoot এর left সমান হয়ে যাবে আমাদের নতুন node
            currentRoot.leftChid = newNode;

            // added কে true করে দিলাম কারণ আমরা নতুন node যুক্ত করে নিলে তো আমাদের আর এই প্রোগ্রাম চালানোর প্রয়োজন নাই তাই।
            added = true;
          }
          // যদি আমাদের currentRoot এর left এ কোনো node থাকে তাহলে
          else {
            // এখন আমাদের currentRoot হয়ে যাবে currenRoot এ থাকা left
            currentRoot = currentRoot.leftChid;
          }
        }
        // যদি আমাদের নতুন node আমাদের tree এর currentRoot এর value থেকে বড় হয় তাহলে
        else if (value > currentRoot.value) {
          // যদি আমাদের currentRoot এর right এ কোনো node না থাকে তাহলে
          if (currentRoot.rightChild === null) {
            // currentRoot এর right সমান হয়ে যাবে আমাদের নতুন node
            currentRoot.rightChild = newNode;

            // added কে true করে দিলাম কারণ আমরা নতুন node যুক্ত করে নিলে তো আমাদের আর এই প্রোগ্রাম চালানোর প্রয়োজন নাই তাই।
            added = true;
          }
          // যদি আমাদের currentRoot এর right এ কোনো node থাকে তাহলে
          else {
            // এখন আমাদের currentRoot হয়ে যাবে currenRoot এ থাকা right
            currentRoot = currentRoot.rightChild;
          }
        }
      }
    }
  }
}

Binary Search Tree - Search Node

\> binary tree তে আমরা যেহেতু জানি যে root থেকে left এর দিকে যেসব সংখ্যা থাকবে সেগুলো সব ছোট হবে root এর চেয়ে এবং right এর দিকে যেসব সংখ্যা থাকবে সেগুলো সব বড় হবে root এর চেয়ে তাহলে আমাদের এখানে search করা খুবই সহজ হয়ে গেছে। আমরা প্রথমে চেক করে নিবো আমাদের root আছে কি না যদি থাকে তাহলে বাকি কাজ করবো না হলে সেখানেই রিটার্ন করে দিবো null। আর যদি থাকে তাহলে আমরা যে node টি খুজতে চাচ্ছি সেটা দিয়ে চেক করবো যে আমাদের root এর চেয়ে বড় নাকি ছোট ওই নতুন value টি যদি বড় হয় তাহলে তো আমরা left এর দিকে যাবো না কারণ আমরা জানি ওইদিকে শুধু ছোট সংখ্যাই আছে আমরা যাবো right এর দিকে এবং সেদিকেই আমাদের search node পেয়ে যাবো আর যদি ছোট হয় তাহলে তো left এর দিকে যাবো। ব্যাস এই সিম্পল কাজ আর কিছু না এবং যখন আমাদের search node পেয়ে যাবো তখন সেটা রিটার্ন করে দিবো।

ওকে নিচে কোড দেওয়া হলো এবং সাথে কমেন্ট করে দেওয়া হলো কোন লাইন কি করছে।

// searching node in binary tree
findNode(value) {
    // চেক করা হচ্ছে যদি আমাদের tree তে কোনো node ই না থাকে তাহলে null রিটার্ন করবে।
    if (!this.root) {
      return null;
    }

    // আমাদের বর্তমান root কে একটি variable এর মধ্যে রাখলাম।
    let currentRoot = this.root;

    // আমাদের root যদি থাকে তাহলে এই while loop চলবে।
    while (currentRoot) {

      // চেক করা হচ্ছে যে আমাদের currentRoot এর যে value আছে যেটা কি আমরা যে node খুজছি সেটার সাথে মিলে?
      if (currentRoot.value === value) {
        // মিলে গেলে আমাদের search node এই currentRoot তাই সেটা রিটার্ন করে দিচ্ছি।
        return currentRoot;
      }
      // চেক করা হচ্ছে আমরা যে node খুজছি সেটা কি আমাদের currentRoot এর value এর থেকে ছোট।
      else if (value < currentRoot.value) {
        // ছোট হলে আমাদের currentRoot করে দিবো currentRoot এ থাকা left কে কারণ আমরা জানি যে আমাদের সব ছোট সংখ্যা রয়েছে left এর দিকে।
        currentRoot = currentRoot.leftChid;
      } else {
        // আর বড় হলে আমাদের currentRoot করে দিবো currentRoot এর right কে কারণ ওইদিকে সব বড় সংখ্যা রয়েছে।
        currentRoot = currentRoot.rightChild;
      }
    }
  }