Constructing a Binary Tree from Traversal Results

by

Posted on 08 December 2016

We can construct a binary tree if we are given at least two traversal results. The first traversal must be the in-order traversal and the second can be either pre-order or post-order traversal.

The in-order traversal result will be used to determine the left and the right child nodes, and the
pre-order/post-order can be used to determine the root node. For example, consider the traversal results given below:

Constructing Binary tree from traversal results

Inorder-INFORMATION

Postorder-INOFMAINOTR

Pre–order Traversal: A B D E C F G

In–order Traversal:    D B E A F C G

Here, we have the in-order traversal sequence and pre-order traversal sequence. Follow the steps given below to construct the tree:

 Step 1 Determine Root

In Pre-Order the first element, in Post-Order the last element is the root node.

PreOrder-Root node ←A B D E C F G

PostOrder-INOFMAINOTR→ Root node

 Step 2 Determine Subtree

Elements on the left side of the root node in the in-order traversal form the left sub-tree of the root node. Similarly, elements on the right side of the root node in the in-order traversal sequence form the right sub-tree of the root node.

(left subtree) D B E  A  F C G (right subtree)

(left subtree) INFO R MATION(right subtree)

 Step 3

Preorder- Recursively select each element from pre-order traversal(make its parent node) , from left to right and create its left and right sub-trees from the in-order traversal. 

Postorder- Recursively select each element from post-order traversal, from right to left and create its left and right sub-trees from in-order traversal. 

 Constructing binary tree form tree traversals

In–order Traversal: D B H E I A F J C G

Post-order Traversal: D H E B I J F G C 

Binary tree from traversal

*underlined letters are considered parent node

Inorder- INFORMATION

Postorder- INOFMAINOTR

binary tree from tree traversal

 *underlined letters are considered parent node

Thank you for reading

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

Also, don't forget to subscribe to our Newsletter.

If you like this article, then please share it and help us grow.


If You Love this article, You Should Consider:

  • Like us on Facebook
  • Follow us on Instagram
  • Follow us on Twitter
  • Subscribe to our Newsletter.
  • Let us know your suggestions and queries in the comments below.

Thank you for your Love and Support

Share your thoughts

Search
Adverstisement
Adverstisement