Given preorder and inorder traversal of a tree, construct the binary tree.

Question Analysis

The problem at hand is a classic tree construction problem, where you are provided with two lists that represent the preorder and inorder traversals of a binary tree. Your task is to reconstruct the original binary tree from these traversals.

• Preorder Traversal: This traversal visits the nodes in the order: Node (Root), Left, Right. Thus, the first element in the preorder list is always the root of the tree.

• Inorder Traversal: This traversal visits the nodes in the order: Left, Node (Root), Right. This means that once you identify the root node from the preorder list, you can find the left and right subtrees by locating the root in the inorder list.

To solve this problem, the key steps involve:

1. Identifying the root node from the preorder list.
2. Using the root node to partition the inorder list into left and right subtrees.
3. Recursively constructing the left and right subtrees using the corresponding segments from the preorder and inorder lists.

Answer

To construct the binary tree from the given preorder and inorder traversal lists, you can use the following Python code:

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 in the preorder list is the root node
    root_val = preorder[0]
    root = TreeNode(root_val)

    # Find the index of the root in the inorder list
    inorder_index = inorder.index(root_val)

    # Recursively construct the left and right subtrees
    root.left = buildTree(preorder[1:inorder_index+1], inorder[:inorder_index])
    root.right = buildTree(preorder[inorder_index+1:], inorder[inorder_index+1:])

    return root

Explanation:

• Step 1: Start by identifying the root of the tree from the first element of the preorder list.

• Step 2: Locate the root node's position in the inorder list. The elements to the left of this position form the left subtree, and the elements to the right form the right subtree.

• Step 3: Recursively apply the above logic to construct the left and right subtrees. Use the slices of the preorder and inorder lists to ensure that the correct subtree elements are passed to each recursive call.

This recursive approach efficiently reconstructs the original binary tree by leveraging the properties of preorder and inorder traversals.