#105

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Construct Binary Tree from Preorder and Inorder Traversal

Construct a binary tree using preorder and inorder traversal arrays, leveraging array scanning and hash table lookups.

array hash table divide and conquer tree binary tree

Problem Statement

You are given two arrays, preorder and inorder, which represent the preorder and inorder traversals of a binary tree. Your task is to reconstruct and return the binary tree. The preorder array gives you the nodes in the order they were visited from top to bottom, while the inorder array tells you the structure, i.e., which nodes are on the left or right of each parent.

Both arrays are guaranteed to represent the same binary tree. The problem asks you to leverage array scanning to process the preorder array and use a hash table for fast lookup to reconstruct the tree structure. The solution should be optimized with a divide-and-conquer approach to handle the maximum constraint efficiently.

Examples

Example 1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Example details omitted.

Example 2

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Example details omitted.

Constraints

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of 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.

Solution Approach

Array Scanning with Preorder

To build the binary tree, start by scanning through the preorder array. The first element in preorder represents the root of the binary tree. After identifying the root, divide the inorder array into left and right subtrees based on the root's position. The left subtree will contain all nodes before the root in inorder, and the right subtree contains all nodes after. This allows you to recursively build the tree by continuing with the next elements from preorder for each subtree.

Hash Table for Fast Lookup

Using a hash table to store the indices of the inorder array significantly speeds up the process. Without this optimization, finding the root's index in the inorder array would require linear scanning. By storing the index of each element in a hash table, you can directly access the position of any element in constant time. This eliminates the need for repeatedly searching the inorder array, improving the time complexity of the solution.

Divide and Conquer Approach

The divide-and-conquer strategy allows us to recursively break down the problem. Each step works on progressively smaller subarrays of preorder and inorder. After determining the root node from preorder, the left and right subtrees can be handled separately, each with its own smaller subtree arrays. This approach ensures that the problem size reduces logarithmically with each recursive step, making the solution more efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(N), where N is the number of nodes in the tree. This is because each node is processed once, and hash table lookups take constant time. The space complexity is also O(N), due to the space needed for the hash table and recursive stack during tree construction.

What Interviewers Usually Probe

Do you understand how to scan the preorder array and use the inorder array to identify subtree structures?
Can you explain how the hash table optimizes the process of finding the root's index in inorder?
Will you handle edge cases like when the tree is very small (1 or 2 nodes)?

Common Pitfalls or Variants

Common pitfalls

Failing to efficiently look up the index of nodes in the inorder array without a hash table can lead to suboptimal solutions.
Not correctly handling the boundary conditions when recursively dividing the preorder and inorder arrays for smaller subtrees.
Assuming the tree always has a specific shape or depth, which could lead to incorrect handling of unbalanced trees.

Follow-up variants

Construct Binary Tree from Preorder and Postorder Traversal
Construct Binary Search Tree from Preorder Traversal
Construct Binary Tree from Level Order and Inorder Traversal

FAQ

What is the primary pattern for this problem?

The key pattern is array scanning combined with hash table lookups. Preorder traversal helps identify roots, and inorder identifies left and right subtrees.

What should I be aware of when dividing the arrays?

Ensure that you correctly divide the arrays into left and right subtrees based on the root's index in inorder. Misplacement can lead to incorrect tree structure.

How does the time complexity improve with a hash table?

Using a hash table allows you to find the root's index in O(1) time, rather than O(N), significantly speeding up the tree construction process.

Can I solve this problem without recursion?

Yes, it is possible to solve this problem iteratively using a stack, but recursion is generally simpler and more intuitive for this specific problem.

How do I handle edge cases like a single node tree?

For a single node, both preorder and inorder arrays will have just one element, and the tree is simply that node itself.

terminal

Solution

Solution 1: Hash Table + Recursion

The first node $preorder[0]$ in the pre-order sequence is the root node. We find the position $k$ of the root node in the in-order sequence, which can divide the in-order sequence into the left subtree $inorder[0..k]$ and the right subtree $inorder[k+1..]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def dfs(i: int, j: int, n: int) -> Optional[TreeNode]:
            if n <= 0:
                return None
            v = preorder[i]
            k = d[v]
            l = dfs(i + 1, j, k - j)
            r = dfs(i + 1 + k - j, k + 1, n - k + j - 1)
            return TreeNode(v, l, r)

        d = {v: i for i, v in enumerate(inorder)}
        return dfs(0, 0, len(preorder))

Continue Practicing

#106 construct binary tree from inorder and postorder traversal #889 construct binary tree from preorder and postorder traversal #108 convert sorted array to binary search tree