Construct Binary Tree from Preorder and Inorder Traversal - Python Solution

1. Introduction

The "Construct Binary Tree from Preorder and Inorder Traversal" problem is an advanced tree construction challenge, often encountered in coding interviews. It tests one's ability to rebuild a binary tree given two traversal sequences: preorder and inorder. This problem is key for understanding how tree data structures and their traversal algorithms work together.

Problem

Given two integer arrays preorder and inorder, which represent the preorder and inorder traversal of a binary tree, the task is to reconstruct and return the original binary tree. Preorder traversal visits a node before its children, and inorder traversal visits the left child, then the node, and then the right child.

2. Solution Steps

1. Understand how preorder and inorder traversals represent a tree.

2. Use the first element of preorder traversal to identify the root of the tree.

3. Locate the root in the inorder sequence to divide the tree into left and right subtrees.

4. Recursively apply the above steps to construct the left and right subtrees.

5. Continue this process until the entire tree is reconstructed.

3. Code Program

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 = TreeNode(preorder[0])
    rootIndex = inorder.index(preorder[0])

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

    return root

# Example Usage
root = buildTree([3,9,20,15,7], [9,3,15,20,7])

Output:

A binary tree with the structure corresponding to the given preorder and inorder traversal arrays.

Explanation:

1. Root Identification: The root of the tree is the first element in the preorder array.

2. Inorder Partitioning: The inorder array is partitioned into two halves at the root's position. The left half represents the left subtree, and the right half represents the right subtree.

3. Recursive Construction: Recursively apply the same logic to construct the left and right subtrees using slices of the preorder and inorder arrays.

4. Tree Reconstruction: The process continues until the entire tree is reconstructed, matching the given traversal orders.