Construct Binary Tree from Preorder and Inorder Traversal – 105. LeetCode

Constructing a binary tree from its preorder and inorder traversals involves rebuilding the tree using the order in which nodes are visited.

Preorder traversal visits the root node first, followed by the left and right subtrees, while inorder traversal visits the left subtree, root, and then the right subtree. By combining the two, we can uniquely reconstruct the binary tree. This is useful for problems where a tree’s structure needs to be determined from its traversal orders, such as restoring data or enabling traversal-based algorithms.

Optimal Algorithm

import java.util.HashMap;
import java.util.Map;

public class ConstructBinaryTreeOptimized {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);
    }

    private TreeNode construct(int[] preorder, int preStart, int preEnd,
                               int[] inorder, int inStart, int inEnd,
                               Map<Integer, Integer> inorderMap) {
        if (preStart > preEnd || inStart > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        int rootIndex = inorderMap.get(root.val);
        int leftTreeSize = rootIndex - inStart;

        root.left = construct(preorder, preStart + 1, preStart + leftTreeSize,
                              inorder, inStart, rootIndex - 1, inorderMap);
        root.right = construct(preorder, preStart + leftTreeSize + 1, preEnd,
                               inorder, rootIndex + 1, inEnd, inorderMap);

        return root;
    }
}

Step 1: Build Hash Map for Inorder Indices

Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
    inorderMap.put(inorder[i], i);
}

• Create a HashMap to store the indices of elements in the inorder array.
  • Key: Value of the node
  • Value: Index of the node in the inorder array.
• This exists to quickly look up the index of the root node in the inorder array, so that we can avoid repeatedly scanning the inorder array.

Step 2: Recursive Helper Function

return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);

• Calls the contruct helper function passing:
  • Preorder and inorder arrays
  • Start and end indices for both arrays.
  • The inorderMap for efficient root lookups.
• Encapsulates the logic for building the tree into dedicated function.

Step 3: Base Case For Recursion

if (preStart > preEnd || inStart > inEnd) return null;

• Checks if the range of indices is invalid.
  • preStart > preEnd: No nodes left in preorder range.
  • inStart > inEnd: No nodes left in the inorder range.

Step 4: Identify the Root Node

TreeNode root = new TreeNode(preorder[preStart]);

• Creates a new TreeNode using the first element of the current preorder range (preorder[preStart]), which is the root of the current subtree.
• The first element in the preorder array represents the root of the tree or subtree (key characteristic of preorder traversal).

Step 5: Locate the Root in the Inorder Array

int rootIndex = inorderMap.get(root.val);

• Retrieves the index of the root node in the inorder array using the hash map.
• The inorder array divides the tree into left and right subtrees:
  • Nodes before rootIndex belong to the left subtree.
  • Nodes after rootIndex belong to the right subtree.

Step 6: Calculate Left Subtree Size

int leftTreeSize = rootIndex - inStart;

• Determines how many nodes belong to the left subtree.
• Helps Identify the range of preorder and inorder indices for recursive calls.

Step 7: Recursive Construction of Subtrees

root.left = construct(preorder, preStart + 1, preStart + leftTreeSize,
                      inorder, inStart, rootIndex - 1, inorderMap);
root.right = construct(preorder, preStart + leftTreeSize + 1, preEnd,
                       inorder, rootIndex + 1, inEnd, inorderMap);

1. Left Subtree
   • Recursive call with updated indices:
     • Preorder: preStart + 1 to preStart + leftTreeSize.
     • inorder: inStart to rootIndex – 1
2. Right Subtree:
   • Recursive call with updated indiced:
     • Preorder: preStart + leftTreeSize + 1 to preEnd.
     • Inorder: rootIndex + 1 to inEnd.

• Divides the problem into small subproblems:
  • Builds left and right subtrees independently.
• Updates the ranges of preorder and inorder arrays to focus on the relevant portions,

Step 8: Return Constructed Tree

return root;

• Returns the constructed subtree rooted at root.

Why This Code Works

This code efficiently reconstructs a binary tree using preorder and inorder traversals. It optimizes performance with a hash map for quick lookups and employs recursion to divide and conquer the problem. The clear separation of logic and efficient data structures ensures adherence to LeetCode best practices.