Construct Tree from PreOrder and Inorder Traversals

105.Construct Binary Tree from Preorder and Inorder

Array

Tree

Divide and Conquer

Problem Statement:

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Key Insights:

1. From preorder:
   • First element is always root node
   • Next elements form left subtree, then right subtree
2. From inorder:
   • Elements before root form left subtree
   • Elements after root form right subtree
   • Can find size of left subtree

Java Solution:

public TreeNode buildTree(int[] preorder, int[] inorder) {
    // Initialize indices for arrays
    int preStart = 0, preEnd = preorder.length - 1;
    int inStart = 0, inEnd = inorder.length - 1;
    
    return build(preorder, inorder, preStart, preEnd, inStart, inEnd);     
}

private TreeNode build(int[] preorder, int[] inorder, 
                                    int preStart, int preEnd, 
                                    int inStart, int inEnd) {
    // Base case: invalid range
    if (preStart > preEnd) return null;
    
    // Root is always at preStart in preorder
    int val = preorder[preStart];
    TreeNode curr = new TreeNode(val);
    
    // Find root in inorder traversal
    int iIndex = -1;
    for (int i = inStart; i <= inEnd; i++) 
        if (inorder[i] == val) 
            iIndex = i;
    
    // Calculate size of left subtree
    int size = iIndex - inStart;
    
    // Recursively build left and right subtrees
    curr.left = build(preorder, inorder, 
                     preStart + 1, preStart + size,  // Left subtree in preorder
                     inStart, iIndex - 1);           // Left subtree in inorder
                     
    curr.right = build(preorder, inorder, 
                      preStart + size + 1, preEnd,   // Right subtree in preorder
                      iIndex + 1, inEnd);            // Right subtree in inorder

    return curr; 
}

Python Solution:

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    
    def build(pre_start, pre_end, in_start, in_end):
        if pre_start > pre_end:
            return None
        
        # Root is first element in preorder
        root_val = preorder[pre_start]
        root = TreeNode(root_val)
        
        # Find root in inorder traversal
        in_index = inorder.index(root_val, in_start, in_end + 1)
        
        # Calculate sizes
        left_size = in_index - in_start
        
        # Build subtrees
        root.left = build(pre_start + 1, pre_start + left_size,
                         in_start, in_index - 1)
                         
        root.right = build(pre_start + left_size + 1, pre_end,
                          in_index + 1, in_end)
        
        return root
    
    return build(0, len(preorder)-1, 0, len(inorder)-1)

C++ Solution:

TreeNode* buildTree(vector<int>>& preorder, vector<int>>& inorder) {
    return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}

TreeNode* build(vector<int>>& preorder, vector<int>>& inorder,
                     int pre_start, int pre_end,
                     int in_start, int in_end) {
                         
    if (pre_start > pre_end) return nullptr;
    
    // Create root node
    int val = preorder[pre_start];
    TreeNode* curr = new TreeNode(val);
    
    // Find root in inorder
    int i_index = find(inorder.begin() + in_start,
                      inorder.begin() + in_end + 1,
                      val) - inorder.begin();
    
    // Calculate subtree size
    int size = i_index - in_start;
    
    // Build subtrees
    curr->left = build(preorder, inorder,
                      pre_start + 1, pre_start + size,
                      in_start, i_index - 1);
                      
    curr->right = build(preorder, inorder,
                       pre_start + size + 1, pre_end,
                       i_index + 1, in_end);
    
    return curr;
}

Complexity:

Time: O(n²) without HashMap, O(n) with HashMap | Space: O(n)

Note: Can optimize by using HashMap to store inorder indices