# Construct Binary Tree from Preorder and Postorder Traversal LeetCode Solution

Difficulty Level Medium

## Problem Statement

Construct Binary Tree from Preorder and Postorder Traversal LeetCode Solution – Given two integer arrays, `preorder` and `postorder` where `preorder` is the preorder traversal of a binary tree of distinct values and `postorder` is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

```Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]```

## Explanation

We know that the first element in the pre array is the root. We also know that the second element in the pre array is the root of the left subtree. Now if we can find this second element in the post array then all elements before it and including it would belong to the left subtree and all elements after it (excluding the last element which is the root) will be the elements in the right subtree. We can apply this logic recursively while processing each element in the pre array and building the tree. We use a hashmap for fast lookups in the post array.

The problem is easier to solve if we decrease it into subproblems using Divide and Conquer.

Given preorder : 1 2 4 5 3 6 and postorder : 4 5 2 6 3 1

We can se it as : 1 ( 2 4 5) ( 3 6 ) and ( 4 5 2 ) ( 6 3 ) 1

## Code

### C++ Code For Construct Binary tree from preorder and postorder traversal

```#define null nullptr
class Solution {
public:
int i = 0;
TreeNode* help(vector<int>& pre, vector<int>& post,int start,int end){
//BAse Case
if(start>end) return null;
if(i>=pre.size()) return null;
int j =-1;
for(int k = start;k<=end;k++)
if(pre[i]==post[k]){
j=k;
break;
}
if(j==-1) return null;
i++;
TreeNode* root = new TreeNode(post[j]);
TreeNode* l = help(pre,post,start,j-1);
root->left=l;
TreeNode* r = help(pre,post,start,j-1);
root->right=r;
return root;
}
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
return help(pre,post,0,post.size()-1);
}
};```

### Python Code For Construct Binary tree from preorder and postorder traversal

```class Solution:
def constructFromPrePost(self, pre, post):
return self.constructFromPrePostRecurUtil(
pre, 0, len(pre) - 1, post, 0, len(post) - 1)

def constructFromPrePostRecurUtil(
self,
pre,
preStart,
preEnd,
post,
postStart,
postEnd):
# Base case.
if (preStart > preEnd):
return None
if (preStart == preEnd):
return TreeNode(pre[preStart])
# Recursive case.
root = TreeNode(pre[preStart])
leftRootIndexInPre = preStart + 1
leftRootIndexInPost = self.getIndexInPost(
post, pre[leftRootIndexInPre])
leftEndIndexInPre = leftRootIndexInPre + \
(leftRootIndexInPost - postStart)
root.left = self.constructFromPrePostRecurUtil(
pre,
leftRootIndexInPre,
leftEndIndexInPre,
post,
postStart,
leftRootIndexInPost)
root.right = self.constructFromPrePostRecurUtil(
pre,
leftEndIndexInPre + 1,
preEnd,
post,
leftRootIndexInPost + 1,
postEnd - 1)
return root

def getIndexInPost(self, post, target):
for i, v in enumerate(post):
if v == target:
return i
return -1   # to optimize
```

### Java Code For Construct Binary tree from preorder and postorder traversal

```class Solution {
public TreeNode helper(int[] pre,int[] post,int psi,int pei,int ppsi,int ppei ) {
if (psi>pei) return null;
TreeNode root=new TreeNode(pre[psi]);
if(psi==pei) return root;
int idx=ppsi;
while(post[idx]!=pre[psi+1]){idx++;}
int tne=idx-ppsi+1;
root.left=helper(pre,post,psi+1,psi+tne,ppsi,idx);
root.right=helper(pre,post,psi+tne+1,pei,idx+1,ppei-1);
return root;
}
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
return helper(preorder,postorder,0,preorder.length-1,0,postorder.length-1);
}
}```

O(nlogn)

O(1)

Translate »