Day 26: Traversing Techniques

Hello Dear Students,
 Hope you all are doing good...

Aaj hum tree traversal ke baare mein study karenge which is very most important question from the exam point of view.

Let's get started...

TRAVERSING - Traversing operation mein hum each and every data element ko visit karte hain. Har ek data element ko access kiya jata hai, atleast once. Traversing operation hota hai jo ki data structure ke elements par perform kiya jata hai. Hum binary tree traversing ko understand karenge because exam mein binary tree traversing ke questions important hain.

BINARY TREE - Binary tree wo tree data structure hota hai jisme maximum 2 child nodes hi ho sakte hain. Isme ek parent node ke 0,1,or 2 child nodes ho sakte hain but 2 se jyada nahi ho sakte. 

BINARY TREE TRAVERSAL - Binary tree traversal means binary tree data structure mein traversing operation ko perform karna. Binary tree ke har ek element ko visit karna. Hum 2 tareeke se traversing kar sakte hain. The 2 traversing methods are as follows-
  1. Pre-order Traversal (Root, Left, Right)
  2. In-order Traversal (Left, Root, Right)
  3. Post-order Traversal (Left, Right, Root)

DEPTH-FIRST TRAVERSAL- Depth-first traversal mein tree ke depth mein jaa kar pehle traversing ki jati hai and then upper and right tree par traversing ki jati hai. 3 methods hain depth-first traversal ke, hum ek binary tree ki example lenge sabhi methods ko understand karne ke liye.

binary tree
Binary Tree

1. Pre-order Traversing -  Pre-order traversal mein hum Root, Left, Right procedure ko follow karte hain. Traversing means har ek element ko visit karna so pre-order traversing mein hum har ek element ko visit karne ke liye sabse pehle Root element ko visit karte hain then left children then right children. For example, above binary tree ko agar hum pre-order traversing method se traverse karenge then,
 Root, Left, Right
 8, 3, 2, 5, 4, 7, 9, 14, 12.
So, above order mein traversing hogi tree ki pre-order traversing method se. 

2. In-Order Traversing - In-order traversing mein hum Left, Root, Right procedure ko follow karte hain. Isme sabse pehle left child node ko visit karte hain then root node ko and then right child nodes ko. For example, above binary tree ko agar hum in-order traversing se traverse karenge then,
 Left, Root, Right
 2, 3, 4, 5, 7, 8, 9, 12, 14
Hum depth-first mein traversing kar rahe hain, so, sabse pehle tree ki depth mein jayenge and then traversing karenge, in-order traversing mein hum sabse pehle tree ki left nodes par visit karenge, then root node par and last mein right nodes par. Means Left-Root-Right.
  • So, sabse pehle 8 root hai but hum 8 ke left mein visit karenge because left ko sabse pehle visit karna hai,
  • 8 ke left mein hai 3 but 3 has child nodes, so left child of 3 is 2, so 2 ko sabse pehle visit karenge,
  • Ab 2 ko traverse kar liya hai and 2 ke koi bhi child node nahi hai so, left ke baad aata hai root, so 2 ka root hai 3,ab 3 ko traverse karenge,
  • Ab 3 ko traverse kar liya, then right, right mein hai 5 but 5 also has child nodes so 5 ke left child ko traverse karenge means 4 ko.
  • Then 4 ke baad root ko traverse karenge which is 5. So, 5 traverse hoga.
  • Ab 5 ke right child mein hai 7, so 7 traverse hoga.
  • Now, left child nodes sabhi traverse ho gayi hain so ab hum root ko traverse karenge means 8.
  • Ab 8 ke baad hum left child ko dekhenge, 8 ka koi bhi left child nahi hai so ab hum right child ko traverse karenge, means 9.
  • 9 ka bhi left child nahi hai so right child is 14 but 14 has left child, so hum 12 ko traverse karenge.
  • And then 14
  • So traverse karne ka order = 2,3,4,5,7,8,9,12,14.
Tips and Tricks - Agar binary search tree hoga, means left child nodes root se less hogi and right child nodes root se big hogi then, agar hum us par in-order traversing karenge then ye ascending order mein ayega . For example, above tree is binary search tree and humne us tree ko in-order traversing se traverse kiya so order is in ascending order.  (Not in all cases but mostly)

3. Post-order Traversing - Post-order traversing mein hum Left, Right, Root procedure ko follow karte hain. Isme hum sabse pehle Left child nodes ko visit karte hain, then right child nodes and then Root node ko. For example, agar hum above binary tree ko post-order traversing mein traverse karenge then,
 Left, Right, Root
 2, 4, 7, 5, 3, 12, 14, 9, 8
Post-order traversing bhi depth-first traversing hoti hai, so, isme bhi hum depthe se ja kar traverse karenge. Post-order mein traversing ka order hota hai, Left-Right-Root means sabse pehle left child nodes then right child nodes and then last is root node. 
  • 8 se start karenge, hum sabse pehle left tree ko traverse karenge so left mein hai 3, but 3 has child nodes so left child node is 2. So, sabse pehle 2 ko traverse karenge.
  • Ab 2 ke baad hum right node ko dekhenge, right node is 5 but 5 also have child nodes, 5 ke left child is 4, so 4 is traversed.
  • Ab 4 ke baad hum right node ko dekhenge, right node is 7, then 7 is traversed.
  • 7 ke baad hum root node ko dekhenge, 7 ki root node hai 5, so then 5 traverse hoga.
  • Ab 5 ki root node hai 3, so then 3 traverse hoga.
  • Now, 8 traverse nahi hoga because 8 to root node hai and hum root ko end mein traverse karenge, so
  • 8 ke left mein dekhenge, ab 8 ki koi bhi left node nahi hai, so 8 ki right nodes dekhenge which is 9 but 9 is also root so hum root ko end mein hi traverse karenge so depth mein 12 hai which is left node, 12 ko traverse karenge
  • 12 ke right mein koi node nahi hai so 12 ki root node ko traverse karenge which is 14,
  • Then 14 ki root node hai 9 so 9 traverse hoga.
  • 9 ki root node hai 8, then 8 traverse hoga.
  • So, every node is traversed or visited atleast once.
  • So traverse karne ka order = 2,4,7,5,3,12,14,9,8.

BREADTH-FIRST TRAVERSAL - Breadth-first traversal mein hum level by level traversing karte hain. Tree ke nodes ke levels hote hain, root node level 0, then its child nodes on level 1, and so on. So agar hum above binary tree ko breadth-first traversal method se traverse karenge then, 
  Level to level
  8, 3, 9, 2, 5, 14, 4, 7, 12.
Breadth-first mein hum ek level poora traverse karne ke baad doosra level ko traverse karenge. 
  • Sabse pehle 8, 8 ke koi bhi sibling nahi hai so 8 ke baad next level traverse hoga,
  • Next level mein jo nodes hain wo hai 3 and 9, 
  • Then next level is 2, 5, and then 14,
  • After that, 4, 7, and 12.
  • So breadth-first traversing is very simple.
  • The order = 8,3,9,2,5,14,4,7,12.

Best of Luck Students,
 Do visit our website regularly for more content and for daily tests.