Unraveling the Mystery: Constructing a Binary Tree from Preorder and Inorder Traversal

The process of reconstructing a binary tree from its preorder and inorder traversals is a captivating problem in computer science. It challenges our understanding of tree structures and requires a systematic approach to restore the original binary tree. In this blog, we will delve into the intricacies of constructing a binary tree from preorder and inorder traversals. We will explore the underlying algorithm, step-by-step, and provide insights through a detailed example.

 

Understanding the Problem:

Before we delve into the solution, let's ensure we have a clear understanding of the preorder and inorder traversals. Preorder traversal visits the root node first, followed by the left subtree and then the right subtree. In contrast, inorder traversal visits the left subtree first, then the root node, and finally the right subtree.

 

The Challenge:

Given the preorder and inorder traversals of a binary tree, our goal is to reconstruct the original binary tree.

 

The Algorithm:

To construct the binary tree, we will employ a recursive approach that involves the following steps:

1. Select the first element from the preorder traversal as the root of the binary tree.
2. Find the index of the root element in the inorder traversal.
3. Divide the inorder traversal into two parts based on the index found in the previous step: the left subtree and the right subtree.
4. Recursively construct the left subtree using the elements from the left part of the inorder traversal and the corresponding elements from the preorder traversal.
5. Recursively construct the right subtree using the elements from the right part of the inorder traversal and the corresponding elements from the preorder traversal.
6. Return the root of the constructed binary tree.

 

Example

To illustrate the algorithm, let's consider the following example:

Preorder traversal: [3, 9, 20, 15, 7] Inorder traversal: [9, 3, 15, 20, 7]

Based on the preorder traversal, we select 3 as the root node. In the inorder traversal, we find that the left subtree contains [9] and the right subtree contains [15, 20, 7].

We recursively construct the left subtree using the preorder traversal [9] and the inorder traversal [9]. The resulting left subtree is a single node with a value of 9.

Next, we recursively construct the right subtree using the preorder traversal [20, 15, 7] and the inorder traversal [15, 20, 7]. We select 20 as the root node for the right subtree and divide the inorder traversal into [15] (left subtree) and [7] (right subtree).

The resulting right subtree consists of a root node with a value of 20 and its right child with a value of 7.

Finally, we combine the root node (3), the left subtree (9), and the right subtree (20 and 7) to form the complete binary tree.

 

Implementation in Java:

Let's begin with the Java implementation of constructing a binary tree from preorder and inorder traversals.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeFromPreorderInorder {
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return construct(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode construct(int[] preorder, int[] inorder, int start, int end) {
        if (start > end) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex++]);

        if (start == end) {
            return root;
        }

        int inIndex = findIndex(inorder, start, end, root.val);

        root.left = construct(preorder, inorder, start, inIndex - 1);
        root.right = construct(preorder, inorder, inIndex + 1, end);

        return root;
    }

    private int findIndex(int[] inorder, int start, int end, int value) {
        for (int i = start; i <= end; i++) {
            if (inorder[i] == value) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinaryTreeFromPreorderInorder solution = new BinaryTreeFromPreorderInorder();

        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};

        TreeNode root = solution.buildTree(preorder, inorder);
        System.out.println("Binary Tree constructed!");

        // Perform any operations on the binary tree if needed
    }
}

 

Implementation in Python:

Next, let's explore the Python implementation of constructing a binary tree from preorder and inorder traversals.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTreeFromPreorderInorder:
    def buildTree(self, preorder, inorder):
        self.preIndex = 0
        return self.construct(preorder, inorder, 0, len(inorder) - 1)

    def construct(self, preorder, inorder, start, end):
        if start > end:
            return None

        root = TreeNode(preorder[self.preIndex])
        self.preIndex += 1

        if start == end:
            return root

        inIndex = inorder.index(root.val)

        root.left = self.construct(preorder, inorder, start, inIndex - 1)
        root.right = self.construct(preorder, inorder, inIndex + 1, end)

        return root

solution = BinaryTreeFromPreorderInorder()

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

root = solution.buildTree(preorder, inorder)
print("Binary Tree constructed!")

# Perform any operations on the binary tree if needed

 

Conclusion:

In this blog, we explored the process of constructing a binary tree from its preorder and inorder traversals. We discussed the algorithm step-by-step and provided implementation examples in both Java and Python. By understanding the algorithm and studying the code snippets, you now have the knowledge to tackle this problem efficiently. Feel free to experiment with different examples and adapt the code to suit your specific requirements.