algoadvance

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Clarifying Questions

  1. What is the format of the tree node? The tree node structure is likely to be something like: 
    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

  2. What are the characteristics of the input arrays? Both preorder and inorder arrays will contain unique values (since they represent a valid binary tree). They will have no duplicates and will be of the same length.

  3. How large can the input arrays be? For the sake of this problem, you may assume the input arrays can have a length up to 2000.

  4. Are the values always valid integers? Yes, the values can represent typical tree node values, which are integers.

Strategy

  1. Understanding Preorder and Inorder:
    • Preorder traversal visits nodes in the order: root -> left -> right.
    • Inorder traversal visits nodes in the order: left -> root -> right.
  2. Reconstructing the Tree:
    • The first element of the preorder list is the root of the tree.
    • Find this root element in the inorder list; elements to the left of this root in inorder are in the left subtree, and elements to the right are in the right subtree.
  3. Recursive Approach:
    • Recursively build the left and right subtrees using the corresponding segments of preorder and inorder lists.

Code

Here’s the Python implementation:

# 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

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    # The first element of preorder is the root of the tree
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    # Find the index of the root in the inorder array
    root_index_inorder = inorder.index(root_val)
    
    # All elements to the left of root_index_inorder in inorder are in the left subtree
    left_inorder = inorder[:root_index_inorder]
    # All elements to the right of root_index_inorder in inorder are in the right subtree
    right_inorder = inorder[root_index_inorder + 1:]
    
    # Divide the preorder list into parts for left and right subtrees
    left_preorder = preorder[1:1 + len(left_inorder)]
    right_preorder = preorder[1 + len(left_inorder):]
    
    # Recursively construct the left and right subtrees
    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)
    
    return root

Time Complexity

  1. Finding the root index in the Inorder list: This takes O(n) where n is the number of elements. However, this can be optimized by using a hashmap (dictionary) to store the indices of each value in the inorder list. This reduces the lookup time to O(1).

  2. Constructing the tree: For each node, we perform constant time operations plus recursive calls. Each element in the preorder and inorder lists is processed once, leading to a time complexity of O(n).

By optimizing the index lookup with a hashmap, the overall complexity can be improved:

```python def buildTree(preorder, inorder): inorder_index_map = {value: index for index, value in enumerate(inorder)}

def helper(pre_left, pre_right, in_left, in_right):
    if pre_left > pre_right:
        return None
    
    # The first element in the current preorder segment is the root
    root_val = preorder[pre_left]
    root = TreeNode(root_val)
    
    # Index of the root in the inorder array
    root_index_inorder = inorder_index_map[root_val]
    
    # Size of the left subtree
    left_subtree_size = root_index_inorder - in_left
    
    # Recursively build the left and right subtree
    root.left = helper(pre_left + 1, pre_left + left_subtree_size, in_left, root_index_inorder - 1)
    root.right = helper(pre_left + 1 + left_subtree_size, pre_right, root_index_inorder + 1, in_right)
    
    return root

return helper(0, len(preorder) - 1, 0, len(inorder) - 1)

Try our interview co-pilot at AlgoAdvance.com