# Construct Binary Tree from Inorder and Postorder/Preorder Traversal

# From INORDER and POSTORDER

Given two integer arrays `inorder`

and `postorder`

where `inorder`

is the inorder traversal of a binary tree and `postorder`

is the postorder traversal of the same tree, construct and return *the binary tree*.

**Algorithm:**

In Postorder, the rightmost element is the root. Search this root in inorder array .Let that index be i ,then left side of i is left subtree and right side of i is right subtree. We use postorder array to create nodes but to construct tree we use inorder array.

**Code:**

`class Solution {`

int index;

public TreeNode buildTree(int[] inorder, int[] postorder) {

index= postorder.length-1;

return build(postorder,inorder,0,postorder.length-1);

}

public TreeNode build(int[] post, int[] in, int start, int end){

if(start>end){

return null;

}

TreeNode node = new TreeNode(post[index]);

index--;

int inIndex=search(in,start,end,node.val);

node.right=build(post,in,inIndex+1,end);

node.left=build(post,in,start,inIndex-1);

return node;

}

public int search(int arr[], int strt, int end, int value)

{

int i;

for (i = strt; i <= end; i++) {

if (arr[i] == value)

return i;

}

return i;

}

}

# From INORDER and PREORDER

Given two integer arrays `preorder`

and `inorder`

where `preorder`

is the preorder traversal of a binary tree and `inorder`

is the inorder traversal of the same tree, construct and return *the binary tree*.

**Code:**

`class Solution {`

int index=0;

public TreeNode buildTree(int[] preorder, int[] inorder) {

return build(preorder,inorder,0,preorder.length-1);

}

public TreeNode build(int[] pre, int[] in, int start, int end){

if(start>end){

return null;

}

TreeNode node = new TreeNode(pre[index]);

index++;

if(start==end){

return node;

}

int inIndex=search(in,start,end,node.val);

node.left=build(pre,in,start,inIndex-1);

node.right=build(pre,in,inIndex+1,end);

return node;

}

public int search(int arr[], int strt, int end, int value)

{

int i;

for (i = strt; i <= end; i++) {

if (arr[i] == value)

return i;

}

return i;

}

}