By Virendra Jadhav
🔍 Problem 1: Construct Binary Tree from Preorder and Inorder Traversal
Problem Statement:
Given two integer arrays preorderand inorder, construct the binary tree and return its root.
Example:
Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]
Output:
3
/ \
9 20
/ \
15 7
🔍 Problem 2: Construct Binary Tree from Inorder and Postorder Traversal
Problem Statement:
Given two integer arrays inorderand postorder, construct the binary tree and return its root.
Example:
Inorder: [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]
Output:
3
/ \
9 20
/ \
15 7
💡 Why Preorder and Postorder Alone Are Not Sufficient
When given preorder and postorder traversals without the inorder sequence, we cannot uniquely build the tree because the position of left and right children becomes ambiguous. Multiple tree structures can result from the same preorder and postorder combinations.
Example:
Preorder: [1, 2]
Postorder: [2, 1]
Possible trees:
- Tree 1: Root 1 with left child 2
- Tree 2: Root 1 with right child 2
Without inorder traversal, we cannot distinguish between these cases.
🔗 Approach for Preorder + Inorder
- Preorder gives the root first.
- Inorder splits the tree into left and right subtrees.
Steps:
- Pick element from preorder as root.
- Find the root in inorder to divide left and right subtrees.
- Recursively build left and right subtrees.
🔗 Approach for Inorder + Postorder
- Postorder gives the root last.
- Inorder splits the tree into left and right subtrees.
Steps:
- Pick element from postorder as root.
- Find the root in inorder to divide left and right subtrees.
- Recursively build left and right subtrees.
👉 Java Solutions
Preorder + Inorder:
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1, map);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, HashMap<Integer, Integer> map) {
if (preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int index = map.get(root.val);
int leftSize = index - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSize, inStart, index - 1, map);
root.right = build(preorder, preStart + leftSize + 1, preEnd, index + 1, inEnd, map);
return root;
}
}
Inorder + Postorder:
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 || postorder.length == 0) return null;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
👉 Java Solutions
Preorder + Inorder:
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1, map);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, HashMap<Integer, Integer> map) {
if (preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int index = map.get(root.val);
int leftSize = index - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSize, inStart, index - 1, map);
root.right = build(preorder, preStart + leftSize + 1, preEnd, index + 1, inEnd, map);
return root;
}
}
}
return build(postorder, 0, postorder.length - 1, 0, inorder.length - 1, map);
}
private TreeNode build(int[] postorder, int postStart, int postEnd, int inStart, int inEnd, HashMap<Integer, Integer> map) {
if (postStart > postEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(postorder[postEnd]);
int index = map.get(root.val);
int leftSize = index - inStart;
root.left = build(postorder, postStart, postStart + leftSize - 1, inStart, index - 1, map);
root.right = build(postorder, postStart + leftSize, postEnd - 1, index + 1, inEnd, map);
return root;
}
}
👉 Python Solutions
Preorder + Inorder:
class Solution:
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None
index_map = {value: idx for idx, value in enumerate(inorder)}
def helper(pre_start, pre_end, in_start, in_end):
if pre_start > pre_end or in_start > in_end:
return None
root_val = preorder[pre_start]
root = TreeNode(root_val)
index = index_map[root_val]
left_size = index - in_start
root.left = helper(pre_start + 1, pre_start + left_size, in_start, index - 1)
root.right = helper(pre_start + left_size + 1, pre_end, index + 1, in_end)
return root
return helper(0, len(preorder) - 1, 0, len(inorder) - 1)
Inorder + Postorder:
class Solution:
def buildTree(self, inorder, postorder):
if not inorder or not postorder:
return None
index_map = {value: idx for idx, value in enumerate(inorder)}
def helper(post_start, post_end, in_start, in_end):
if post_start > post_end or in_start > in_end:
return None
root_val = postorder[post_end]
root = TreeNode(root_val)
index = index_map[root_val]
left_size = index - in_start
root.left = helper(post_start, post_start + left_size - 1, in_start, index - 1)
root.right = helper(post_start + left_size, post_end - 1, index + 1, in_end)
return root
return helper(0, len(postorder) - 1, 0, len(inorder) - 1)
👉 C++ Solutions
Preorder + Inorder:
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> indexMap;
for (int i = 0; i < inorder.size(); i++) {
indexMap[inorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1, indexMap);
}
TreeNode* build(vector<int>& preorder, int preStart, int preEnd, int inStart, int inEnd, unordered_map<int, int>& indexMap) {
if (preStart > preEnd || inStart > inEnd) return nullptr;
TreeNode* root = new TreeNode(preorder[preStart]);
int index = indexMap[root->val];
int leftSize = index - inStart;
root->left = build(preorder, preStart + 1, preStart + leftSize, inStart, index - 1, indexMap);
root->right = build(preorder, preStart + leftSize + 1, preEnd, index + 1, inEnd, indexMap);
return root;
}
};
Inorder + Postorder:
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int, int> indexMap;
for (int i = 0; i < inorder.size(); i++) {
indexMap[inorder[i]] = i;
}
return build(postorder, 0, postorder.size() - 1, 0, inorder.size() - 1, indexMap);
}
TreeNode* build(vector<int>& postorder, int postStart, int postEnd, int inStart, int inEnd, unordered_map<int, int>& indexMap) {
if (postStart > postEnd || inStart > inEnd) return nullptr;
TreeNode* root = new TreeNode(postorder[postEnd]);
int index = indexMap[root->val];
int leftSize = index - inStart;
root->left = build(postorder, postStart, postStart + leftSize - 1, inStart, index - 1, indexMap);
root->right = build(postorder, postStart + leftSize, postEnd - 1, index + 1, inEnd, indexMap);
return root;
}
};
👏 Final Thoughts
These two problems are great exercises for mastering recursive tree construction. Remember, preorder and inorder or inorder and postorder give enough information to uniquely build a binary tree. But preorder and postorder alone are insufficient.
I hope this guide helped you! If you want more detailed explanations, you can check out my Hashnode blog:
Happy Coding! 🚀
Top comments (0)