#58 Medium Time O(n) Space O(n) Animated

Construct Binary Tree from Preorder and Inorder Traversal

Build binary tree from preorder and inorder traversal arrays.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Tree traversal with recursive contracts

Ask each subtree for exactly the information its parent needs, then combine the two answers.

Approach: Hash Map + Divide and Conquer

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Ask each subtree for exactly the information its parent needs, then combine the two answers.

Common Pitfall

Define the base case before combining left and right subtree results.

Description

Build binary tree from preorder and inorder traversal arrays.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Hash Map + Divide and Conquer

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Define what one recursive call returns.
Handle an empty node.
Recurse into children.
Combine the child results at the current node.

def buildTree(preorder, inorder):
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = 0
    
    def build(left, right):
        nonlocal pre_idx
        if left > right:
            return None
            
        root_val = preorder[pre_idx]
        root = TreeNode(root_val)
        pre_idx += 1
        
        mid = inorder_map[root_val]
        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)
        return root
        
    return build(0, len(inorder) - 1)

Kth Smallest Element in a BST

Binary Tree Maximum Path Sum

Construct Binary Tree from Preorder and Inorder Traversal

Steps

Description

Constraints

Tags

Solution — Hash Map + Divide and Conquer