Construct a binary tree from given Inorder and Postorder Traversal

Objective: Given a inorder and postorder traversal, write an algorithm to construct a binary tree from that. This problem was asked in the Microsoft coding competition.

Input: Inorder and postorder traversals

Similar Problems: Make a Binary Tree from Given Inorder and Preorder Traveral.

Appraoch:

int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };

int[] postOrder = { 4, 5, 2, 6, 7, 3, 1 };.

  • Last element in the postorder [] will be the root of the tree, here it is 1.
  • Now the search ele­ment 1 in inorder[], say you find it at posi­tion i, once you find it, make note of ele­ments which are left to i (this will con­struct the left­sub­tree) and ele­ments which are right to i ( this will con­struct the rightSubtree).
  • Suppose in previous step, there are X number of elements which are left of ‘i’ (which will construct the leftsubtree), take first X elements from the postorder[] traversal, this will be the post order traversal for elements which are left to i. similarly if there are Y number of elements which are right of ‘i’ (which will construct the rightsubtree), take next Y elements, after X elements from the postorder[] traversal, this will be the post order traversal for elements which are right to i
  • From previous two steps construct the left and right subtree and link it to root.left and root.right respectively.
  • See the picture for better explanation.
    Construct-tree-from-Inorder-and-postorder-traversal
    Construct-tree-from-Inorder-and-postorder-traversal

Complete Code:

import java.util.LinkedList;
import java.util.Queue;
public class InorderPostOrderToTree {
public static int pIndex = 0;
public Node makeBTree(int[] inOrder, int[] postOrder, int iStart, int iEnd,
int postStart, int postEnd) {
if (iStart > iEnd || postEnd > postEnd) {
return null;
}
int rootValue = postOrder[postEnd];
Node root = new Node(rootValue);
pIndex++;
if (iStart == iEnd) {
return root;
}
int index = getInorderIndex(inOrder, iStart, iEnd, root.data);
root.left = makeBTree(inOrder, postOrder, iStart, index 1, postStart,
postStart + index (iStart + 1));
root.right = makeBTree(inOrder, postOrder, index + 1, iEnd, postStart
+ index iStart, postEnd 1);
// }
return root;
}
public int getInorderIndex(int[] inOrder, int start, int end, int data) {
for (int i = start; i <= end; i++) {
if (inOrder[i] == data) {
return i;
}
}
return 1;
}
public void printINORDER(Node root) {
if (root != null) {
printINORDER(root.left);
System.out.print(" " + root.data);
printINORDER(root.right);
}
}
public static void main(String[] args) throws java.lang.Exception {
int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };
int[] postOrder = { 4, 5, 2, 6, 7, 3, 1 };
InorderPostOrderToTree i = new InorderPostOrderToTree();
Node x = i.makeBTree(inOrder, postOrder, 0, inOrder.length 1, 0,
postOrder.length 1);
System.out.println("inorder traversal of constructed tree : ");
i.printINORDER(x);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}

Output:

inorder traversal of constructed tree : 
  4  2  5  1  6  3  7

1 thought on “Construct a binary tree from given Inorder and Postorder Traversal”

Leave a Reply to Kabir Sahni Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.