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]

1. From the preorder representation, we know the root is 3.
2. Looking at the inorder representation, we can see that 9 is in the left subtree and 15,20,7 are in the right subtree.
3. 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].

1. The map would be {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}.
2. Calling build(preorder, 0, 4, inorder, 0, 4, map) gives us the root node 3, and splitting the subsequences into [9] for the left subtree, and [15, 20, 7] for the right subtree.
3. 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.

1. Building the map: The time complexity is O(n), where n is the length of the inorder array. This is because we iterate over the inorder array once to build the map.

2. Constructing the tree: We go through each element exactly once in both preorder and inorder arrays to construct the tree, which gives O(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:

1. Map storage: We need O(n) space to store the map.

2. Recursive calls: The maximum depth of recursion tree is n (when the given tree is skewed tree), hence O(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:

1. Identify the root of the tree/subtree from the preorder traversal.
2. Use the root to split the inorder traversal into left and right subtrees.
3. 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.