# Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// Start typing your Java solution below
// DO NOT write main() function
if(inorder.length==0){
return null;
}

//last element of postorder is the root
TreeNode root = new TreeNode(postorder[postorder.length-1]);
//find the root element in the inorder array
//elements occur before it are in its left sub-tree
//elements occur after it are in its right sub-tree
int index = 0;
for(int i=0;i<inorder.length;i++){
if(inorder[i]==root.val){
index = i;
break;
}
}
int[] leftInOrder = new int[index];
int[] leftPostOrder = new int[index];
int[] rightInOrder = new int[inorder.length-index-1];
int[] rightPostOrder = new int[inorder.length-index-1];

for(int i=0;i<inorder.length;i++){
if(i<index){
leftInOrder[i] = inorder[i];
}
if(i>index){
rightInOrder[i-index-1] = inorder[i];
}
}

for(int i=0;i<postorder.length-1;i++){
if(i<index){
leftPostOrder[i] = postorder[i];
}else{
rightPostOrder[i-index]=postorder[i];
}
}

root.left = buildTree(leftInOrder,leftPostOrder);
root.right = buildTree(rightInOrder,rightPostOrder);
return root;
}
}```
Share