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.

Learn more about Tree, Divide and Conquer and Binary Tree patterns.

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.

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.

Solution Implementation

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).

Learn more about how to find time and space complexity quickly using problem constraints.