Conversion of Binary Tree Traversal

Creation of Binary Tree from Preorder to Inorder

Preorder to in-order traversal

Steps

  1. Scan Preorder traversal from L->R.
  2. For each node scanned locate its position in inorder traversal, let the scanned node be x.
  3. The node proceeding x in-order from its left subtree and node succeeding it is from its right subtree.
  4. Repeat step 1 to 3 for each symbol in preorder.
working of tree conversion

Node A

npde a

Node B

node b

Node D

node d

Node H

node h

Node E

node e

Node C,F G

node c.f,g

Final Inorder Traversal Tree

Final Inorder Traversal Tree

Creation of Binary Tree from Post-order to In-order

Steps :

  1. Scan Postorder traversal from R->L.
  2. For each node scanned locate its position in inorder traversal, let the scanned node be x.
  3. The node proceeding x in-order from its left subtree and node succeeding it’s from its right subtree.
  4. Repeat step 1 to 3 for each symbol in preorder.

Given that :

Post-order to In-order

Node A

Node A

Node E

Node E

Node F

Node F

Node H

Node A H

Node C

Node C

Node G

Node  G

Node B

Node B

Node D

Node D

Final Inorder Traversal Tree

Final In-order Traversal Tree

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top