Construct a full binary tree from a preorder and postorder sequence

A full binary tree is a tree in which every node has either 0 or 2 children. Write an efficient algorithm to construct a full binary tree from given preorder and postorder sequence.


 

For example,


Input:

Preorder traversal  : { 1, 2, 4, 5, 3, 6, 8, 9, 7 }
Postorder traversal : { 4, 5, 2, 8, 9, 6, 7, 3, 1 }

 
Output: Full binary tree

Full Binary Tree

 
We can construct a unique binary tree from inorder and preorder sequences, as well as from the inorder and postorder sequences. But preorder and postorder sequences don’t provide enough information to create a unique binary tree. Several binary trees can be constructed due to ambiguity.

For example, consider following skewed trees

        a         a
       /           \
      b             b
     /               \
    c                 c
   /                   \
  d                     d

For both above trees, the preorder and postorder traversal results in same sequence of numbers:

    preorder  : { a, b, c, d }
    postorder : { d, c, b, a }

Therefore, it is not possible to construct a unique binary tree with the help of preorder and postoder sequences. However, a unique full binary tree can easily constructed with them. To illustrate, consider below preorder and postorder sequence –

    preorder  : { 1, 2, 4, 5, 3, 6, 8, 9, 7 }
    postorder : { 4, 5, 2, 8, 9, 6, 7, 3, 1 }

We know that root is the first element in preorder sequence and the last element in postorder sequence. Therefore, the root node is 1. Then we locate the next element in preorder sequence, which must be the left child of the root node. In this case, the left child is 2. Now since 2 is root node of the left subtree, all nodes before 2 in the postorder sequence must be present in the left subtree of the root node i.e. {4, 5, 2} and all the nodes after 2 (except the last) must be present in right subtree i.e. {8, 9, 6, 7, 3}. Now the problem is reduced to building the left and right subtrees and linking them to the root node.

Left subtree:

    Postorder : {4, 5, 2}
    Preorder  : {2, 4, 5}

Right subtree:

    Postorder : {8, 9, 6, 7, 3}
    Preorder  : {3, 6, 8, 9, 7}

 
The idea is to recursively follow the above approach until the complete tree is constructed. This is demonstrated below in C++:

 

Download   Run Code

Output:

Inorder Traversal: 4 2 5 1 8 6 9 3 7

 
Note that above algorithm will ensure a unique binary tree only when all keys in the given preorder/postorder sequence are distinct. For example, two full binary trees exists for following preorder and postorder sequences whose node keys are not distinct.

Preorder traversal  : { 0, 1, 1, 1, 1 }
Postorder traversal : { 1, 1, 1, 1, 0 }

       0
      / \
     1   1
    / \
   1   1
   
   
     0
    / \
   1   1
      / \
     1   1

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of