SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
53 views
in Examples, Exercises and Projects by (562 points)
edited by
  1. Binary tree traversals
  • Inorder traversal
  • Postorder Traversal
  • Preorder Traversal 
  1. Formation of binary tree from its traversals. 
  2. Merging two binary trees together

1 Answer

0 like 0 dislike
by (562 points)
edited by
 
Best answer
  1. Traversals in Binary tree

  • The traversal operation is frquently used operation on a binary tree.
  •  This operation is used to visit each node in the tree exactly once. 
  • There are 6(six) possible ways a tree can be traversed and they are as follows:
  1. R   T T
  2. ​​​​TL   R   TR
  3. TL  T R​​​​​​​​​
  4. TR  TL  R
  5. TR  R    TL  
  6.  R  TR  TL    

 where, TL is left sub-treesof the node R. 

           TR is right sub-trees of the node R. 

  • Out of these six possible traversals, only three are fundamental , they are categorized as given below:
  1. R   T T (preorder) 
  2. TL  R    TR (inorder) 
  3. TL  TR   R (post order) 

Example:

Inorder

1) The given binary tree is 

 Binary tree

Find out the inorder, preorder and postorder traversals.

Solution:

Inorder:Left  root right

Step:1 LC RC

Step:2 _B_A RC

Step:3 DBHEARC

Step:4 DBHEA_C_

Step:5 DBHEAIFJCG

Step:6 DBHEAIFJCG


Algorithm

  1. ptr=ROOT
  2. if(ptr≠NULL) then
  3. inorder(ptr→LC) 
  4. visit(ROOT) 
  5. inorder(ptr→RC) 
  6. end if
  7. stop

Preoder:Root  LC  RC

Step:1 A LC RC

Step:2 B_   C  _

Step:3 ABDEH CFIJG

Step:4 ABDEHCFIJG

Step:5 ABDEHCFIJG

Algorithm

  1. ptr=ROOT
  2. if(ptr≠NULL) then
  3. visit(ROOT) 
  4. preorder(ptr→LC) 
  5. preorder(ptr→RC) 
  6. end if
  7. stop

Postorder : LC  RC Root 

Step:1 LC RC A

Step:2 DHEIJEGC A

Step:3 DHEBIJEGCA

Step:4 DHEBIJEGCA 

Algorithm

  1. ptr=ROOT
  2. if (ptr≠NULL) then
  3. postorder(ptr→LC) 
  4. postorder(ptr→RC) 
  5. visit(ROOT) 
  6. end if
  7. stop

2) To construct inorder, preoder and post order traversals for below binary tree:

binary tree

Solution: 

Inorder: left root right 

Step:1 LC n6 RC 

Step:2 n1 n2 n3 nn5 n6 nnn9 

Step:3 n1 n2 n3 n4 n5  n6 nnn9 

Preoder: Root LC RC 

Step:1 n6 LC RC 

Step:2 n6 n2 n1 n4 n3 nn9 nn 

Step:3 n6 n2 nn4 n3 n5 n9 nn8​​​​​​​​​​​  

Postorder:LC  RC root 

Step1:  LC RC n6 

Step:2 nn3 n5 n4 n2  nnnn6 

Step:3 n1 n3 n5 n4 n2 n8 nnn6


  1. Formation of Binary tree from its traversals​​

  • From a single traversal, it is not possible to construct a unqiue binary tree. 
  • But, if two traversals are known then, we can construct a unique binary tree. 
  • Out of two traversals, one should be inorder traversal and another preorder or postorder. 
  • If the  two traversals are preorder and postorder then, a  binary tree cannot be constructed uniquely. 

Example 1:

Construct the binary tree from the inorder and preorder traversals of a binary tree as given below:

Inorder:D B H E A I F J C G 

Preoder:A B D E H C F I J G 

Solution:

The following steps need to be followed:

  1. From the preoder traversal, it is evident that A​​​​​​ is the root node. 
  2. In inorder traversal, all the nodes  which are on the left side of belong to the left sub tree and those which are on right side of A belong to the right subtree. 
  3. Now the problem reduces to form subtreees and the same procedure can be applied repeatedly. 

Step:1 

binary tree

Step:2

(i) In left subtree , B will be the root(D E H) 

(ii) In right subtree, C will be the root(C F I J G) 

BINARY TREE

Step:3

(i) In right subtree of B, E is the root from the preoder E H. 

From inorder, H will be left subtree of E. 

steps for binary tree

(ii) From left subtree of C, F is the root from the preorder F I J

From inorder, I is left of F and J is right of F. So, 

steps for binary tree

So, the final binary tree from inorder and preorder is 

binary tree


Example:2

Construct a binary tree from the inorder and postorder traversals given below:

Inorder: n1  n nn4  nnn7  n8  n9 

Postorder: n1 n3 n n4  n2 n8  n7 n9 n6

 Solution:

Step:1

n6 is the root from postorder.

Left subtree:​​​​ ​​​​​​ n1  n2 nnn5 

Right subtree: n7  n n

step 1

Step:2

From postorder : n2 is the root of left subtree. 

From postorder: n9 is the root for right subtree. 

step 2

Step:3 

n4 is the root of n2 right subtree. 

n7 is the root of n9 left subtree. 

binary tree


  1. Merging two binary trees together

  • Merge operation is applicable to trees which are reprsented by using a linked structure . 
  • There are two ways that this operation can be carried out. 

Approach 1:

Suppose T1 and T2 are two binary trees. T2 can be merged with T1 if all the nodes from T2, one by one , are inserted into the binary tree T1  

Approach 2:

When the entire tree T2 can be include as a subtree of T1 To achieve this, we need that in either tree . There must be atleast one null subtree. 

(i) Before performing merging, we have to test for compatibility. If in both trees the root node has both the left and  right subtrees, then the merge  will be fail. 

(ii) If T1 has left subtree(right  subtree) empty. Then T2 will be added to the left subtree(the right subtree) of the T1 and vice-versa. 

(iii) If T1 is a tree with n1 nodes and T2 is a tree with n2 nodes. Then the resultant tree T after merging is

T(n1+n2) =T1(n1) +T2(n2

steps for binary tree

FINAL TREE

If the binary tree contains an arithmetic expression, 

Then ,its

  • Inorder will give infix expression
  • Preorder will give prefix expression
  • Postorder will give postfix expression. 

Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...