### 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**

**(**

(since Left nodes of a Tree are read first, then Right nodes and then

**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

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**

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,

----------------------------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,

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.

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.

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 tree; 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.

**Enjoy !!!!**

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

## Post a Comment