How can one create a binary tree with the knowledge of its preorder and inorder traversals?

Question Analysis

The question is asking about constructing a binary tree when given its preorder and inorder traversal sequences. This is a common type of problem in coding interviews that tests a candidate's understanding of tree data structures and recursion.

Understanding the problem requires familiarity with the following concepts:

• Preorder Traversal: In preorder traversal, the nodes are recursively visited in this order: root, left, right.
• Inorder Traversal: In inorder traversal, the nodes are recursively visited in this order: left, root, right.

Given these sequences, the task is to reconstruct the original binary tree. The challenge lies in identifying the root and the subtrees at each recursive step.

Answer

To construct a binary tree from its preorder and inorder traversal sequences, follow these steps:

1. Identify the Root:

   • The first element of the preorder sequence is the root of the tree.

2. Locate the Root in Inorder Sequence:

   • Find the position of this root element in the inorder sequence. This divides the inorder sequence into two parts: the left subtree elements (before the root) and the right subtree elements (after the root).

3. Recursively Construct Subtrees:

   • Use the left part of the inorder sequence to construct the left subtree.
   • Use the right part of the inorder sequence to construct the right subtree.
   • The preorder sequence can be used to determine the roots of these subtrees.

4. Recursive Implementation:

   • Use the identified root and the divided sequences to recursively build the tree.

Here is a concise implementation in Python:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        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
    root_value = preorder[0]
    root = TreeNode(root_value)

    # Find the index of the root in inorder
    mid = inorder.index(root_value)

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

    return root

Key Points:

• The preorder sequence helps in determining the root of the current subtree.
• The inorder sequence helps in determining the boundary between the left and right subtrees.
• The recursive approach allows for the construction of the entire tree from its traversal sequences.