Construct a Binary Tree from In-order and Post-order traversals.

How to construct a Binary Tree from given In order and Post order traversals.

---

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Two traversals are given as input,

  int inOrder[] =   {20, 30, 35, 40, 45, 50, 55, 60, 70};
  int postOrder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};

By using above 2 given In order and Post Order traversal, construct Binary Tree like shown below,

First let us understand what does In order and Post order traversal mean?

---

In-order traversal is traversing a Tree in which Left Node is read first, then root node and then right node and hence the In-order traversal of above tree is,


In-order traversal : 20  30  35  40  45  50  55  60  70

Post-order traversal is traversing a Tree in which Left Node is read first, then right node and then
root node and hence the Post-order traversal of above tree is,
Post-order traversal : 20  35  30  45  40  55  70  60  50

From the above example, we can see that 
Root element will be present at the last in Post-order traversal 
(20  35  30  45  40  55  70  60  50)
(since Left nodes of a Tree are read first, then Right nodes and then Root Node.)

So root node will be present at last, but by simply looking at given Post order traversal it is not possible to identify which element is left child/sub-tree of root node and right child/sub-tree of root node as we are not aware of exact position where the left nodes started and ended in Post-order traversal. 

For finding the Left and Right child's we will use In-order traversal.
So with the help of alone Post-order or Pre-order, it is not possible to build a Tree, we require In-order for finding Left and Right child'/sub-tree.

More details on In Order and Level Order traversal: In Order and Post Order Traversal.

Algorithm

---

We just saw that last element of Post order traversal is root node.

Step 1:
Read the last element from Post order traversal which is root node.
Now, we come to know which is root node.(in our case it is 50)

Step 2: 
Search the same element (element 50) in In-order traversal, 
when the element is found in In-order traversal, then we can very well say that all the elements present before the node found are Left children/sub-tree and all the elements present after the node found are Right children/sub-tree of node found. (as in In-order traversal Left child's are read first and then root node and then right nodes.)

In our example,  
(20, 30, 35, 40, 45)  will be part of Left Sub-tree of Node 50.
(55, 60, 70) will be part of Right Sub-tree of Node 50.

Now we got the fresh inOrder array (20, 30, 35, 40, 45) and (55, 60, 70)
Repeat the  Step 1 and Step 2 for new inOrder arrays.

So, keeping the above rule in mind, 
We will find the root node from Post-order traversal and then left child's and right child's from In-order traversals like shown below, 

So if we repeat the process, we will get our Binary Tree ready.
See image below for detailed explanation,

How we will decide the number of elements from inOrder array and postOrder array will be the part of Left sub-tree and Right sub-tree in each iteration.

---

 

From the above image, we can see that Node 50 in In-order array divides the Tree in 2 parts,
Left sub-tree and Right sub-tree.

So, first we saw that last element in postOrder array is a rootNode, 

checking the same node in inOrder array will give you 2 trees.

Lets call position of element 50 found in inOrder array as INDEX 

Let us understand what this 2 lines mean in below program

node.setLeft(constructTreeFromInOrderAndPostOrder(inOrder, inStart, index-1, postOrder, postStart, (postStart + numberOfNodes)-1));
node.setRight(constructTreeFromInOrderAndPostOrder(inOrder, index+1, inEnd, postOrder, postStart + numberOfNodes, postEnd-1));

Left Subtree

---

1. inOrder array

    1. left sub tree start index = inStart

    2. left sub tree end index  = 

        all the elements present before element found.

        (element found is Node 50 in our  example)
        So in general we can say, index of element found in inOrder array (INDEX) - 1

2. postOrder array

    1. left sub tree start index = postStart
    2. right sub tree end index =

         1. first calculate how much element is present in left subtree
             (INDEX - inStart = numberOfElements  present in Left subtree)
         2. postStart + numberOfElements = this will give us the last index of the element that need to

             be considered. (endIndex)
         3. we need to do -1 in endIndex because when we did INDEX - inStart in step 1, 

             we actually calculated from index point, which should be eliminated as that will not be part 

             of left subtree.
             Example : Node 50 divides the tree in 2 parts, index of node 50 is 5, 

                              now when we calculate INDEX - inStart = 5 - 0 = 5
                              So it says there are 5 elements present in left sub-tree which is including Node 50,
                              but in Left sub-tree of Node 50, we need to exclude it.
          4. So right sub tree end index = (postStart + numberOfElements) - 1.

Right Subtree

---

 1. inOrder array

    1. Right sub tree start index = index of element found in inOrder array (INDEX) + 1
    2. right sub tree end index = end

2. postOrder array

    1. left sub tree start index =

           1. calculating startIndex of right sub-tree is simple,
               It will be endIndex of left sub-tree + 1.
               = left sub tree end index + 1.
               = (INDEX - 1)                  + 1 = INDEX.

 
    2. right sub tree end index = endIndex - 1.
        endIndex - 1, because every time we need to remove one element from endIndex,
        which will be forming a root Node.

Java Program to construct a Binary Tree from given Inorder and Post order traversals.

---

package javabypatel;

public class Node {
 private int data;
 private Node left;
 private Node right;
 private Node nextRight;

 public Node(int data) {
  this.data=data;
 }

 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getLeft() {
  return left;
 }
 public void setLeft(Node left) {
  this.left = left;
 }
 public Node getRight() {
  return right;
 }
 public void setRight(Node right) {
  this.right = right;
 }
 public Node getNextRight() {
  return nextRight;
 }
 public void setNextRight(Node nextRight) {
  this.nextRight = nextRight;
 }
}

ConstructBinaryTreeFromInOrderAndPostOrderTraversal.java

package javabypatel;

public class ConstructBinaryTreeFromInorderAndPostOrderTraversal {

 public static void main(String[] args) {
  new ConstructBinaryTreeFromInorderAndPostOrderTraversal();
 }

 public ConstructBinaryTreeFromInorderAndPostOrderTraversal() {
  int inOrder[] =   {20, 30, 35, 40, 45, 50, 55, 60, 70};
  int postOrder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};
 
  Node n = constructTree(inOrder, postOrder);
  System.out.println(n);
 }


 private static Node constructTree(int[] inOrder, int[] preorder) {
  return constructTreeFromInOrderAndPostOrder(inOrder, 0, inOrder.length-1, preorder, 0, preorder.length-1);
 }

 private static Node constructTreeFromInOrderAndPostOrder(int[] inOrder, int inStart, int inEnd, int[] postOrder, int postStart, int postEnd) {
  if(postStart > postEnd){
   return null;
  }

  Node node = new Node(postOrder[postEnd]);

  int index=0;
  for (int i = inStart; i <= inEnd; i++) {
   if(postOrder[postEnd]==inOrder[i]){
    index = i;
    break;
   }  
  }
  
  int numberOfNodes = index - inStart;
  
  node.setLeft(constructTreeFromInOrderAndPostOrder(inOrder, inStart, index-1, postOrder, postStart, (postStart + numberOfNodes)-1));
  node.setRight(constructTreeFromInOrderAndPostOrder(inOrder, index+1, inEnd, postOrder, postStart + numberOfNodes, postEnd-1));

  return node;
 }
}

You may also like to see

---

Construct a Binary Tree from In-order and Pre-order traversals.

Construct a Binary Tree from In-order and Level-order traversals. 

Top Binary tree interview questions in Java

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.