Construct Binary Tree from Preorder and Inorder Traversal

To build the binary tree from given preorder and inorder traversal arrays, you can follow these steps:

  1. Start with the first element of the preorder array, which will be the root of the tree.
  2. Find the root in the inorder array. The elements to the left of the root in the inorder array will form the left subtree, and the elements to the right of the root will form the right subtree.
  3. Recursively apply the above steps for the left and right subtrees.

Here’s the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def build(pre_left, pre_right, in_left, in_right):
            if pre_left > pre_right or in_left > in_right:
                return None
            
            root_val = preorder[pre_left]
            root = TreeNode(root_val)
            root_index = inorder_dict[root_val]

            left_tree_size = root_index - in_left

            root.left = build(pre_left + 1, pre_left + left_tree_size, in_left, root_index - 1)
            root.right = build(pre_left + left_tree_size + 1, pre_right, root_index + 1, in_right)

            return root

        inorder_dict = {value: idx for idx, value in enumerate(inorder)}
        return build(0, len(preorder) - 1, 0, len(inorder) - 1)

Here’s a brief explanation of the code:

  • The function build constructs the tree recursively using the given boundaries in the preorder and inorder arrays.
  • We use a dictionary inorder_dict to quickly find the index of an element in the inorder array.
  • The recursive process continues by dividing the arrays into left and right subtrees until the boundaries are not valid (i.e., the base case when pre_left > pre_right or in_left > in_right).