Construct Binary Tree from Inorder and Postorder/Preorder Traversal

Abhinay Gupta
2 min readJul 8, 2021

--

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;
}
}

--

--

Abhinay Gupta

Exploring personal growth, tech, and culture through engaging storytelling | Inspiring and connecting with readers worldwide.