Can you devise a binary tree given its preorder and inorder traversals?

Question Analysis

The problem requires you to reconstruct a binary tree from its preorder and inorder traversal sequences. To solve this, you need to understand the properties of tree traversals:

• Preorder Traversal: Visits nodes in the order: root, left subtree, right subtree. The first element in the preorder sequence is always the root of the tree.
• Inorder Traversal: Visits nodes in the order: left subtree, root, right subtree. This traversal helps in identifying the boundary between the left and right subtrees of the root node.

With these properties, you can recursively determine the structure of the binary tree. The key steps include identifying the root from the preorder list and then using the inorder list to divide the remaining nodes into left and right subtrees.

Answer

To construct the binary tree from given preorder and inorder traversal sequences, you can use the following algorithm:

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 preorder is always the root.
    root_val = preorder.pop(0)
    root = TreeNode(root_val)

    # Find the index of the root in inorder list to divide left and right subtrees.
    inorder_index = inorder.index(root_val)

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

    return root

Explanation:

• Base Case: If either the preorder or inorder list is empty, return None (indicating no tree node).
• Root Identification: The first element of the preorder list is the root. Remove this element from the preorder list for subsequent recursive calls.
• Subtree Division: Find the index of the root in the inorder list. This index divides the list into two parts; the left part corresponds to the left subtree and the right part corresponds to the right subtree.
• Recursive Construction: Recursively construct the left and right subtrees using the divided inorder list and the modified preorder list.

This approach effectively uses the properties of the traversal sequences to reconstruct the tree in a recursive manner.