Construct Binary Tree from Preorder and Inorder Traversal - Java Solution

1. Introduction

This post examines a fascinating problem in binary tree algorithms - constructing a binary tree from given preorder and inorder traversal arrays. This problem is a great example of how tree traversals can be used to reconstruct the original tree structure, a concept crucial in fields like computational biology and syntax tree construction in compilers.

Problem

Given two integer arrays preorder and inorder, which are the preorder and inorder traversals of a binary tree, the task is to reconstruct and return the original binary tree. It's assumed that no two elements in the tree are the same.

2. Solution Steps

1. Use the first element of the preorder array as the root.

2. Find this root element in the inorder array to divide the tree into left and right subtrees.

3. Recursively apply the process to construct the left and right subtrees.

4. Utilize a map to optimize the search for the root element in the inorder array.

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

3. Code Program

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

    TreeNode(int x) {
        val = x;
    }
}

public class ConstructBinaryTreePreorderInorder {
    int preorderIndex;
    Map<Integer, Integer> inorderIndexMap;

    public static void main(String[] args) {
        ConstructBinaryTreePreorderInorder treeBuilder = new ConstructBinaryTreePreorderInorder();
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        TreeNode root = treeBuilder.buildTree(preorder, inorder);
        // Output can be verified through in-order traversal or other tree traversal methods
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preorderIndex = 0;
        // Build a hashmap to store value -> its index relations in inorder
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        return arrayToTree(preorder, 0, preorder.length - 1);
    }

    private TreeNode arrayToTree(int[] preorder, int left, int right) {
        if (left > right) return null;

        // Select the preorder_index element as the root and increment it
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);

        // Build left and right subtree, excluding inorderIndexMap[rootValue] element because it's the root
        root.left = arrayToTree(preorder, left, inorderIndexMap.get(rootValue) - 1);
        root.right = arrayToTree(preorder, inorderIndexMap.get(rootValue) + 1, right);
        return root;
    }
}

Output:

The output will be the root of the reconstructed binary tree. The tree structure can be verified through tree traversal methods.

Explanation:

1. buildTree: This function initializes the process to reconstruct the binary tree from preorder and inorder traversals.

2. A hashmap (inorderIndexMap) is created to store the indices of elements in the inorder array for quick access.

3. The function arrayToTree is called to build the tree recursively.

4. arrayToTree: This recursive function constructs the tree. It uses the preorderIndex to determine the root node and splits the tree into left and right subtrees based on the root's index in the inorder traversal.

5. The function assigns the left and right children recursively and returns the root node.

6. The reconstruction process efficiently builds the tree by splitting it into smaller subtrees and connecting them to form the final binary tree.