Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal
Problem Explanation
This problem is asking to build a binary tree from given preorder and inorder traversal representations.
In a preorder traversal of a binary tree, the root is visited first, followed by the left subtree, and then the right subtree. In other words, if you have the preorder traversal representation of a tree, then the first element in the representation would be the root of the tree.
In an inorder traversal, the left subtree is visited first, followed by the root, and then the right subtree. So, in the inorder traversal representation, the position of the root divides the tree's elements into two parts: the elements to the left of the root are in the left subtree and the elements to the right are in the right subtree.
Example Walkthrough
Let's walk through an example using the following inputs:
1 2 3preorder = [3,9,20,15,7] 4inorder = [9,3,15,20,7]
- From the preorder representation, we know the root is
3
. - Looking at the inorder representation, we can see that
9
is in the left subtree and15,20,7
are in the right subtree. - We then recursively do the same process for the left and right subtrees.
Solution Approach
The solution uses a recursive approach. It starts by identifying the root from the preorder representation and uses that to split the inorder representation into left and right subtrees. A map is used to quickly locate the root in the inorder representation. It then continues this process recursively on the two subtrees.
Here is the pseudo-code of this process:
1
2
31. Initialize a map with element to index mapping for inorder traversal.
42. Define a recursive function (build) that takes in the subarray boundaries (preStart, preEnd, inStart, inEnd).
5 - Base case: If preStart > preEnd, return null.
6 - Get the root value from preorder[preStart] and find its index in the inorder traversal using the map.
7 - Construct a new TreeNode with the root value.
8 - Determine the size of the left subtree from the inorder index of the root.
9 - Recursively build the left and right subtrees, and assign them to the left and right children of the root node.
103. Call the build function with the full array boundaries to construct the tree.
Example
Let's return to our earlier example with preorder = [3,9,20,15,7]
and inorder = [9,3,15,20,7]
.
- The map would be
{9: 0, 3: 1, 15: 2, 20: 3, 7: 4}
. - Calling
build(preorder, 0, 4, inorder, 0, 4, map)
gives us the root node3
, and splitting the subsequences into[9]
for the left subtree, and[15, 20, 7]
for the right subtree. - Recursively building these two subtrees eventually results in this tree:
1 2 3 3 4 / \ 5 9 20 6 / \ 7 15 7
Python Solution
1 2python 3class Solution: 4 def buildTree(self, preorder, inorder): 5 in_map = {num: idx for idx, num in enumerate(inorder)} 6 7 def helper(pre_left, pre_right, in_left, in_right): 8 if pre_left > pre_right: 9 return None 10 root_val = preorder[pre_left] 11 in_idx = in_map[root_val] 12 root = TreeNode(root_val) 13 # Indices in preorder are shifted by +1 as the first one is the root. 14 root.left = helper(pre_left + 1, pre_left + in_idx - in_left, in_left, in_idx - 1) 15 root.right = helper(pre_left + in_idx - in_left + 1, pre_right, in_idx + 1, in_right) 16 return root 17 18 return helper(0, len(preorder) - 1, 0, len(inorder) - 1)
Java Solution
1 2java 3public class Solution { 4 int preIndex = 0; 5 int[] preorder; 6 int[] inorder; 7 Map<Integer, Integer> inMap = new HashMap<>(); 8 9 public TreeNode buildTree(int[] preorder, int[] inorder) { 10 this.preorder = preorder; 11 this.inorder = inorder; 12 13 // build a map from value to index for inorder traversal 14 int idx = 0; 15 for (Integer val : inorder) 16 inMap.put(val, idx++); 17 18 return helper(0, inorder.length - 1); 19 } 20 21 private TreeNode helper(int inStart, int inEnd) { 22 if (inStart > inEnd) return null; 23 24 // choose preIndex location's element as root and move to next 25 int rootVal = preorder[preIndex++]; 26 TreeNode root = new TreeNode(rootVal); 27 28 // build left and right subtrees 29 root.left = helper(inStart, inMap.get(rootVal) - 1); 30 root.right = helper(inMap.get(rootVal) + 1, inEnd); 31 return root; 32 } 33}
JavaScript Solution
1 2javascript 3var buildTree = function(preorder, inorder) { 4 let map = new Map(); 5 inorder.forEach((val, idx) => { 6 map.set(val, idx); 7 }); 8 9 function helper(preStart, preEnd, inStart, inEnd) { 10 if (preStart > preEnd || inStart > inEnd) return null; 11 12 let rootVal = preorder[preStart]; 13 let inIdx = map.get(rootVal); 14 let leftSize = inIdx - inStart; 15 16 let root = new TreeNode(rootVal); 17 root.left = helper(preStart + 1, preStart + leftSize, inStart, inIdx - 1); 18 root.right = helper(preStart + leftSize + 1, preEnd, inIdx + 1, inEnd); 19 return root; 20 } 21 22 return helper(0, preorder.length - 1, 0, inorder.length - 1); 23};
C++ Solution
1
2c++
3class Solution {
4public:
5 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
6 unordered_map<int, int> inMap;
7 for(int i = 0; i < inorder.size(); i++)
8 inMap[inorder[i]] = i;
9
10 return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inMap);
11 }
12
13private:
14 TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& inMap) {
15 if(preStart > preEnd)
16 return nullptr;
17
18 int rootVal = preorder[preStart];
19 int rootInIndex = inMap[rootVal];
20 int leftSize = rootInIndex - inStart;
21
22 TreeNode* root = new TreeNode(rootVal);
23 root->left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootInIndex - 1, inMap);
24 root->right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootInIndex + 1, inEnd, inMap);
25 return root;
26 }
27};
C# Solution
1
2csharp
3public class Solution {
4 Dictionary<int, int> inMap = new Dictionary<int, int>();
5 int preIndex = 0;
6
7 public TreeNode BuildTree(int[] preorder, int[] inorder) {
8 for(int i = 0; i < inorder.Length; i++)
9 inMap[inorder[i]] = i;
10
11 return Helper(preorder, 0, inorder.Length - 1);
12 }
13
14 private TreeNode Helper(int[] preorder, int inStart, int inEnd) {
15 if(inStart > inEnd)
16 return null;
17
18 int rootVal = preorder[preIndex++];
19 TreeNode root = new TreeNode(rootVal);
20
21 root.left = Helper(preorder, inStart, inMap[rootVal] - 1);
22 root.right = Helper(preorder, inMap[rootVal] + 1, inEnd);
23 return root;
24 }
25}
These solutions all follow the same approach we just discussed. They first build a map for quick look-up of the root's index in the inorder array. Then they recursively build the left and right subtrees by adjusting subarray boundaries using the root and its position in the inorder array.
Hopefully, this was helpful in understanding how to construct a binary tree given its preorder and inorder traversal.# Analyzing Time and Space Complexity
Time Complexity
The time complexity depends on two main operations in these solutions: building the map and constructing the tree.
-
Building the map: The time complexity is
O(n)
, wheren
is the length of theinorder
array. This is because we iterate over theinorder
array once to build the map. -
Constructing the tree: We go through each element exactly once in both
preorder
andinorder
arrays to construct the tree, which givesO(n)
time complexity.
Combining both operations, the overall time complexity of these solutions is O(n) + O(n) = O(n)
.
Space Complexity
The space complexity is also O(n)
, where n
is the length of the inorder
array. Here's why:
-
Map storage: We need
O(n)
space to store the map. -
Recursive calls: The maximum depth of recursion tree is
n
(when the given tree is skewed tree), henceO(n)
space for the call stack.
Hence, the overall space complexity of these solutions is O(n)
.
Conclusion
Constructing a binary tree from its preorder
and inorder
traversals allows us to reveal the initial structure of the tree before it was traversed. This problem is an excellent example of how we can use recursion and hashmap to efficiently and cleanly solve a problem.
Remember, the key steps are:
- Identify the root of the tree/subtree from the
preorder
traversal. - Use the root to split the
inorder
traversal into left and right subtrees. - Apply these processes recursively to the left and right subtrees.
By applying these steps, we can reconstruct the complete binary tree from only its traversal information.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.