**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 element 1 in
*inorder[]*, say you find it at position*i*, once you find it, make note of elements which are left to*i*(this will construct the leftsubtree) and elements which are right to*i*( this will construct 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.

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

good work!is the worst case complexity O(n^2)?