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.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
Constraints:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder and inorder consist of unique values.inorder also appears in preorder.preorder is guaranteed to be the preorder traversal of the tree.inorder is guaranteed to be the inorder traversal of the tree.In #105 Construct Binary Tree from Preorder and Inorder Traversal, the key insight comes from understanding the properties of the two traversals. In preorder, the first element always represents the root of the current subtree. In inorder, elements to the left of the root belong to the left subtree, while elements to the right belong to the right subtree.
A common approach is to use recursion with divide and conquer. First, identify the root from the preorder array. Then locate that value in the inorder array to determine the boundaries of the left and right subtrees. To speed up lookups, store inorder indices in a hash map. Recursively construct the left and right subtrees using the corresponding ranges in the traversal arrays.
This strategy processes each node once, leading to efficient performance. With a hash map for quick index access, the algorithm runs in O(n) time with O(n) additional space for recursion and the lookup structure.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive Divide and Conquer with Hash Map | O(n) | O(n) |
| Recursive without Hash Map (linear search in inorder) | O(n^2) | O(n) |
take U forward
This approach uses recursion to build the tree. We know that the first element of the preorder traversal is the root of the tree. We find that element in the inorder traversal to determine the elements of the left and right subtrees. We then recursively build the left and right subtrees.
Steps:
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is processed once.
Space Complexity: O(n) for the recursion call stack and additional structures.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def buildTree(self, preorder, inorder):
9 def helper(preorder_start, preorder_end, inorder_start, inorder_end):
10 if preorder_start > preorder_end:
11 return None
12
13 root_val = preorder[preorder_start]
14 root = TreeNode(root_val)
15 inorder_root_index = inorder_index_map[root_val]
16 left_tree_size = inorder_root_index - inorder_start
17
18 root.left = helper(preorder_start + 1, preorder_start + left_tree_size, inorder_start, inorder_root_index - 1)
19 root.right = helper(preorder_start + left_tree_size + 1, preorder_end, inorder_root_index + 1, inorder_end)
20
21 return root
22
23 inorder_index_map = {value: idx for idx, value in enumerate(inorder)}
24 n = len(preorder)
25 return helper(0, n - 1, 0, n - 1)This Python solution defines a TreeNode class and constructs the tree using a helper function. The helper function takes indices to track the ranges in the preorder and inorder lists, creating new TreeNode objects as necessary and using an index map for efficient lookups. This approach recursively builds the tree, taking care of each node's left and right subtrees.
This approach uses an iterative method to build the binary tree using stacks. By leveraging the properties of the preorder and inorder sequences, we can keep track of the tree nodes that are yet to be processed. We utilize a stack data structure to maintain the hierarchy of nodes as they are constructed.
Steps:
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the stack and additional data structures like the map for indices.
1#include <unordered_map>
2#include <vector>
3#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) return nullptr;
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < inorder.size(); ++i) {
inorderIndexMap[inorder[i]] = i;
}
stack<TreeNode*> st;
TreeNode* root = new TreeNode(preorder[0]);
st.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.size(); ++i) {
TreeNode* node = st.top();
if (inorderIndexMap[node->val] != inorderIndex) {
node->left = new TreeNode(preorder[i]);
st.push(node->left);
} else {
while (!st.empty() && inorderIndexMap[st.top()->val] == inorderIndex) {
node = st.top();
st.pop();
++inorderIndex;
}
node->right = new TreeNode(preorder[i]);
st.push(node->right);
}
}
return root;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Preorder traversal always reveals the root of the current subtree first, while inorder traversal shows how nodes are split between the left and right subtrees. Combining these two pieces of information uniquely determines the structure of the binary tree. This property allows the original tree to be reconstructed.
Yes, this problem is a common medium-level tree question in technical interviews, including FAANG companies. It tests understanding of tree traversal properties, recursion, and divide-and-conquer strategies. Interviewers often expect candidates to optimize the solution using a hash map.
A hash map is commonly used to store the index of each element in the inorder traversal for fast lookups. This prevents repeated scanning of the inorder array and reduces the overall time complexity. Recursion is then used to build the binary tree structure.
The optimal approach uses recursion with a hash map to store the index of each value in the inorder traversal. The preorder array identifies the root of each subtree, while the inorder array determines left and right subtree boundaries. This allows the tree to be reconstructed efficiently in O(n) time.
This C++ solution employs an iterative approach using a stack. By iterating through the preorder list, it constructs the tree and manages left and right children using the stack. This method avoids recursion and utilizes an index map for inorder positions.