105. Construct Binary Tree from Preorder and Inorder Traversal


Problem Description

The given LeetCode problem involves two integer arrays, preorder and inorder, which represent the preorder and inorder traversals, respectively, of a binary tree. The task is to reconstruct the original binary tree based on these traversals.

In a preorder traversal, the nodes are visited in the following order: root node, left subtree, and then right subtree. In an inorder traversal, the nodes are visited in this order: left subtree, root node, and then the right subtree.

The challenge here is that trees can be constructed in an almost infinite number of ways, but there is exactly one binary tree that led to these specific preorder and inorder traversals. The goal is to find and return that original binary tree structure.

Intuition

When we consider the arrays given, the first element of the preorder array is always the root of the tree because in the preorder traversal, the root node is visited first.

Knowing the root, we can find the root element's index in the inorder array. This index divides the inorder array into two parts: all elements to the left are part of the left subtree, and all elements to the right are part of the right subtree.

We can use this information to define the boundaries of the left and right subtrees in both arrays. For the preorder array, the elements after the root until the number of elements in the left subtree of the inorder array are the elements of the left subtree. The remaining elements form the right subtree.

Using a recursive function, we can keep dividing the problem into smaller subproblems. Each call constructs a node with a value from the preorder array, and calls itself recursively to create the left and right children using the corresponding parts of the preorder and inorder arrays.

To optimize the process of finding the root element's index in the inorder array, the solution uses a hash table ("dictionary" in Python), mapping values to their respective indices in the inorder array. This allows for constant-time lookups instead of linear-time searches.

Each recursive call carries the indices indicating which portion of the arrays to use for constructing the left and right subtrees, alongside with the number of elements in the current subtree (n). If n becomes zero, it means we are at a leaf, and we return None to indicate the absence of a subtree.

Overall, the recursion reconstructs the binary tree by attaching left and right children appropriately to each node until the whole tree is built.

Solution Approach

The solution implements a recursive algorithm heavily relying on the knowledge of tree traversal and an efficient data structure—a dictionary in Python—to optimize the search process.

Recursive Function dfs

The dfs function is a recursive function that performs the following actions:

  • It first checks whether the subtree to be created has any nodes (n > 0). If n is 0, the function returns None, as there are no nodes to construct in this subtree.
  • It creates a new node with the value of the root from the preorder array (v = preorder[i]).
  • It finds the index of this root value in the inorder array using the previously constructed dictionary (k = d[v]).
  • It calculates the left and right subtree sizes and recursively calls itself to create the left subtree (l) and the right subtree (r).
  • The recursive call for the left subtree uses the current index i + 1 in preorder and the start index j in inorder. The size of the left subtree is determined by the difference of indices in inorder (k - j).
  • Similarly, the recursive call for the right subtree adjusts the starting index in preorder by adding the size of the left subtree (i + 1 + k - j) and sets the start index in inorder just after the root's index (k + 1). The size (n - k + j - 1) is determined taking into account the elements that were already part of the left subtree and the root.
  • Finally, it constructs and returns a new TreeNode with value v, left child l, and right child r.

Dictionary for Index Lookup

In the main body of the buildTree function, before starting the recursive process, a dictionary d is created that maps every value in inorder to its corresponding index. This dictionary is used to quickly find the root's index in the inorder array during each recursive call.

Return Value

After all the setup, the dfs function is initially called with the arguments (0, 0, len(preorder)), which represents the entire tree, and the result of this call is the root of the reconstructed tree. The dfs function continues to build the tree and connect all sub-nodes recursively, and finally, the tree is returned.

Conclusion

This recursive approach efficiently rebuilds the binary tree from its preorder and inorder traversals by leveraging the properties of these traversals and using a dictionary for swift index lookups, thus avoiding the need for a linear search each time a root node is to be found in the inorder list.

💪
Level Up Your
Algo Skills

Example Walkthrough

To illustrate the solution approach, let's consider a simple binary tree.

Given the following traversal arrays:

  • preorder = [3, 9, 20, 15, 7]
  • inorder = [9, 3, 15, 20, 7]

We want to reconstruct the binary tree from these.

Here's how the algorithm works step by step:

  1. Starting with the root:

    • The first element in the preorder array is 3, which is the root node of the binary tree.
  2. Building a dictionary for index lookup:

    • The dictionary d for the inorder array is created: {9:0, 3:1, 15:2, 20:3, 7:4}.
  3. Dividing the inorder array into left and right subtrees:

    • For the root node 3, the dictionary d gives us the index 1. Hence, inorder[0] is in the left subtree, and inorder[2:] is in the right subtree.
  4. Recursive calls to construct subtrees:

    • The dfs function will be first called with (0, 0, 5) representing the entire tree.
    • The first call will use 3 as the root node, and we'll have two recursive calls:
      • For the left subtree: dfs(1, 0, 1) (since there's only one element in the left subtree, which is 9).
      • For the right subtree: dfs(2, 2, 3) (which corresponds to elements [15, 20, 7] in the inorder array).
  5. Constructing the left subtree for the first call (root node):

    • The recursive call dfs(1, 0, 1) will find a root with a value 9 (since preorder[1] is 9). This subtree has no further left or right children since n is 1.
  6. Constructing the right subtree for the first call (root node):

    • The recursive call dfs(2, 2, 3) will find the root 20 (since preorder[2] is 20). The dictionary tells us 20 is at index 3 in inorder. So the left subtree will be [15] and the right subtree [7].
      • For 20's left child, dfs is called with (3, 2, 1), which will simply return the node with value 15.
      • For 20's right child, dfs is called with (4, 4, 1), which will simply return the node with value 7.
  7. Constructing and returning the final tree:

    • The calls return the subtrees which are connected to their respective parents. Ultimately, the initial dfs call assembles the entire tree and returns the root node (3).

The final structure is as follows:

1    3
2   / \
3  9  20
4    /  \
5   15   7

This is the binary tree that corresponds to the provided preorder and inorder traversal arrays. The algorithm efficiently rebuilds this tree structure through recursion and utilizing a dictionary for quick index lookup.

Python Solution

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: List[int], inorder: List[int]) -> Optional[TreeNode]:
9        # Helper function to construct tree recursively
10        def construct_tree(preorder_index: int, inorder_index: int, tree_size: int):
11            # Base case: if no elements to consider
12            if tree_size <= 0:
13                return None
14          
15            # Get the root value from the preorder traversal
16            root_value = preorder[preorder_index]
17          
18            # Find the root value's index in the inorder traversal
19            inorder_root_index = value_to_index[root_value]
20          
21            # Construct the left subtree
22            left_subtree = construct_tree(preorder_index + 1, inorder_index, inorder_root_index - inorder_index)
23          
24            # Construct the right subtree
25            right_subtree = construct_tree(preorder_index + 1 + inorder_root_index - inorder_index, 
26                                           inorder_root_index + 1, 
27                                           tree_size - inorder_root_index + inorder_index - 1)
28          
29            # Return the constructed tree node
30            return TreeNode(root_value, left_subtree, right_subtree)
31      
32        # Create a dictionary to map values to their indices in inorder traversal for easy look-up
33        value_to_index = {value: i for i, value in enumerate(inorder)}
34      
35        # Start constructing the tree from the first element in the preorder list
36        return construct_tree(0, 0, len(preorder))
37

Java Solution

1class Solution {
2    private int[] preorderTraversal; // Array to hold the preorder traversal of the tree
3    private Map<Integer, Integer> inorderIndices = new HashMap<>(); // Map to hold the indices of values in inorder traversal
4
5    // Builds the binary tree given preorder and inorder traversal arrays
6    public TreeNode buildTree(int[] preorder, int[] inorder) {
7        int n = preorder.length; // The number of nodes in the tree
8        this.preorderTraversal = preorder; // Assigning preorder traversal array to the class variable for global access in this context
9      
10        // Mapping each value from inorder array to its index for quick lookup
11        for (int i = 0; i < n; ++i) {
12            inorderIndices.put(inorder[i], i);
13        }
14        // Initiates the recursive tree building process from the whole range of given arrays
15        return buildTreeRecursive(0, 0, n);
16    }
17
18    // Recursive method to build the binary tree
19    private TreeNode buildTreeRecursive(int preorderStart, int inorderStart, int size) {
20        if (size <= 0) { // Base case: if there are no elements to consider, return null
21            return null;
22        }
23      
24        // Fetching the current value from the preorder array (root of the subtree)
25        int rootValue = preorderTraversal[preorderStart];
26        // Getting the index of the current root in the inorder array
27        int inorderRootIndex = inorderIndices.get(rootValue);
28        // Calculating the number of nodes in the left subtree
29        int leftSubtreeSize = inorderRootIndex - inorderStart;
30
31        // Building the left subtree recursively
32        TreeNode leftSubtree = buildTreeRecursive(preorderStart + 1, inorderStart, leftSubtreeSize);
33      
34        // Building the right subtree recursively
35        // Need to move past the left subtree in the preorder array, hence "preorderStart + 1 + leftSubtreeSize"
36        TreeNode rightSubtree = buildTreeRecursive(preorderStart + 1 + leftSubtreeSize, inorderRootIndex + 1, size - 1 - leftSubtreeSize);
37
38        // Creating the current root node with computed left and right subtrees
39        return new TreeNode(rootValue, leftSubtree, rightSubtree);
40    }
41}
42
43/**
44 * Definition for a binary tree node.
45 * A basic TreeNode class defining the structure of each node in the binary tree.
46 */
47class TreeNode {
48    int val; // The value of the node
49    TreeNode left; // Pointer to the left child
50    TreeNode right; // Pointer to the right child
51
52    // Constructor for creating a leaf node with a specific value
53    TreeNode(int val) { 
54        this.val = val; 
55    }
56
57    // Constructor for creating a node linked to its children
58    TreeNode(int val, TreeNode left, TreeNode right) {
59        this.val = val;
60        this.left = left;
61        this.right = right;
62    }
63}
64

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <functional>
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
18        int nodeCount = preorder.size();
19        unordered_map<int, int> nodeIndexMap;
20        // Build a hash map to efficiently find the index of any element in inorder
21        for (int i = 0; i < nodeCount; ++i) {
22            nodeIndexMap[inorder[i]] = i;
23        }
24
25        // Recursive lambda to build the tree given a range in preorder and inorder
26        function<TreeNode*(int preorderStart, int inorderStart, int size)> buildSubTree =
27            [&](int preorderStart, int inorderStart, int size) -> TreeNode* {
28            if (size <= 0) {
29                return nullptr; // Subtree has no nodes
30            }
31
32            int rootVal = preorder[preorderStart];        // Get the current root value
33            int inorderIndex = nodeIndexMap[rootVal];     // Find root value's index in inorder
34
35            // Recursively build the left subtree
36            TreeNode* leftChild = buildSubTree(preorderStart + 1, inorderStart, inorderIndex - inorderStart);
37
38            // Recursively build the right subtree
39            TreeNode* rightChild = buildSubTree(preorderStart + 1 + inorderIndex - inorderStart, inorderIndex + 1, size - 1 - (inorderIndex - inorderStart));
40
41            return new TreeNode(rootVal, leftChild, rightChild); // Construct the node with its subtrees
42        };
43
44        return buildSubTree(0, 0, nodeCount); // Initialize recursion from the root
45    }
46};
47
48// NOTE: TreeNode and Solution classes should be included in the same namespace or in the global scope.
49

Typescript Solution

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    val: number;
6    left: TreeNode | null;
7    right: TreeNode | null;
8
9    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
10        this.val = val;
11        this.left = left;
12        this.right = right;
13    }
14}
15
16/**
17 * Constructs a binary tree from preorder and inorder traversal arrays.
18 * 
19 * @param {number[]} preorder - The preorder traversal array of the tree.
20 * @param {number[]} inorder - The inorder traversal array of the tree.
21 * @return {TreeNode | null} The constructed binary tree's root node.
22 */
23function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
24    // Create a map to efficiently find the index of values in the inorder array.
25    const indexMap: Map<number, number> = new Map();
26    const nodeCount = inorder.length;
27
28    // Fill the map with the element as the key and index as the value.
29    for (let i = 0; i < nodeCount; ++i) {
30        indexMap.set(inorder[i], i);
31    }
32
33    /**
34     * Recursive helper function to construct the binary tree.
35     * 
36     * @param {number} preStart - The current index in the preorder array.
37     * @param {number} inStart - The current index in the inorder array.
38     * @param {number} size - The number of nodes to consider for the current subtree.
39     * @return {TreeNode | null} The constructed subtree's root node.
40     */
41    const buildSubTree = (preStart: number, inStart: number, size: number): TreeNode | null => {
42        // Base case: if there are no elements to construct the subtree, return null.
43        if (size <= 0) {
44            return null;
45        }
46
47        // Retrieve the root value of the current subtree from the preorder array.
48        const rootValue = preorder[preStart];
49        // Find the index of the root value in the inorder array.
50        const rootIndex = indexMap.get(rootValue)!;
51
52        // Calculate the left subtree size.
53        const leftSize = rootIndex - inStart;
54
55        // Recursively construct the left subtree.
56        const leftSubtree = buildSubTree(preStart + 1, inStart, leftSize);
57        // Recursively construct the right subtree.
58        const rightSubtree = buildSubTree(preStart + 1 + leftSize, rootIndex + 1, size - 1 - leftSize);
59
60        // Create the root node with the constructed left and right subtrees.
61        return new TreeNode(rootValue, leftSubtree, rightSubtree);
62    };
63
64    // Start building the tree from the beginning of preorder and inorder arrays.
65    return buildSubTree(0, 0, nodeCount);
66}
67

Time and Space Complexity

Time Complexity

The time complexity of the given recursive function is O(N), where N is the number of nodes in the tree. Since each node in the tree is processed exactly once, the main operations include:

  1. Fetching the preorder value: O(1) per node,
  2. Locating the inorder index from the hashmap: O(1) per node.

The recursive process continues until all nodes are processed. Due to the use of the hashmap for storing and retrieving the index of each value, the access is in constant time, bypassing the need for a linear search which would otherwise result in O(N^2) time complexity if done naively.

Space Complexity

The space complexity of the function is O(N) for the following reasons:

  1. Hashmap d stores N key-value pairs representing each node's value and index in the inorder traversal.
  2. The recursion stack may grow up to O(N) in the case of a skewed tree (where each node has only one child).
  3. The output structure, which is a binary tree that contains N TreeNode instances.

Thus, the overall space complexity, which includes the space required for the recursion call stack and the space for the hashmap, is O(N).

😈
Become an
Algo Monster

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.


TA 👨‍🏫