Construct Tree from Preorder and Inorder

▶

Steps

setup

Initialize root and stack

Create the root node with the first preorder value (3) and initialize the stack with this root. Set inorder_index to 0 to track position in inorder array.

💡 The root is always the first preorder element; stack helps track nodes to attach children to.

Line:

root = TreeNode(preorder[0])
stack = [root]
inorder_index = 0

💡 Root node creation anchors the tree; stack starts with root to manage child attachments.

fill_cells

Process preorder value 9: attach as left child

Look at next preorder value 9. Top of stack is node 3, which does not match inorder[inorder_index] (9). Attach 9 as left child of 3 and push it onto stack.

💡 When top of stack's value differs from inorder[inorder_index], we add left children to build left subtree.

Line:

node = stack[-1]
if node.val != inorder[inorder_index]:
    node.left = TreeNode(val)
    stack.append(node.left)

💡 Left children are added while preorder node differs from inorder node at current index.

compare

Process preorder value 20: pop stack to attach right child

Next preorder value is 20. Top of stack is 9, which matches inorder[inorder_index] (9). Pop 9 from stack and increment inorder_index to 1.

💡 When stack top matches inorder[inorder_index], it means left subtree is complete; we pop to attach right child next.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    node = stack.pop()
    inorder_index += 1

💡 Popping signals completion of left subtree nodes and readiness to attach right children.

fill_cells

Attach 20 as right child of 3

After popping 9, top of stack is 3 which matches inorder[inorder_index] (3). Pop 3 and increment inorder_index to 2. Attach 20 as right child of 3 and push it onto stack.

💡 We continue popping while top matches inorder to find correct parent for right child.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    node = stack.pop()
    inorder_index += 1
node.right = TreeNode(val)
stack.append(node.right)

💡 Right children are attached after popping nodes matching inorder to move to right subtree.

fill_cells

Process preorder value 15: attach as left child of 20

Next preorder value is 15. Top of stack is 20, which does not match inorder[inorder_index] (15). Attach 15 as left child of 20 and push it onto stack.

💡 When top of stack differs from inorder[inorder_index], attach left child to build left subtree.

Line:

node = stack[-1]
if node.val != inorder[inorder_index]:
    node.left = TreeNode(val)
    stack.append(node.left)

💡 Left children are added until stack top matches inorder element.

compare

Process preorder value 7: pop stack to attach right child

Next preorder value is 7. Top of stack is 15, which matches inorder[inorder_index] (15). Pop 15 and increment inorder_index to 3.

💡 Matching stack top and inorder means left subtree under 20 is complete; pop to attach right child.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    node = stack.pop()
    inorder_index += 1

💡 Popping signals readiness to attach right child after finishing left subtree.

fill_cells

Pop 20 and attach 7 as right child

Top of stack is 20 which matches inorder[inorder_index] (20). Pop 20 and increment inorder_index to 4. Attach 7 as right child of 20 and push it onto stack.

💡 Continue popping to find correct parent for right child 7.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    node = stack.pop()
    inorder_index += 1
node.right = TreeNode(val)
stack.append(node.right)

💡 Right children are attached after popping nodes matching inorder to move to right subtree.

compare

Finalize construction: pop 7 and increment inorder_index

Top of stack is 7, which matches inorder[inorder_index] (7). Pop 7 and increment inorder_index to 5, which is beyond inorder length, indicating completion.

💡 Popping last node matching inorder means all nodes processed and tree construction is complete.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    node = stack.pop()
    inorder_index += 1

💡 When inorder_index reaches length, construction is complete.

reconstruct

Return the root node

All preorder nodes processed and stack is empty. Return the root node representing the fully constructed binary tree.

💡 Returning root allows traversal or other operations on the constructed tree.

Line:

return root

💡 The root node now points to the entire constructed tree.

reconstruct

Final tree structure and answer

The tree is fully constructed with root 3, left child 9, and right subtree rooted at 20 with children 15 and 7. This matches the expected output.

💡 This final step confirms the tree matches preorder and inorder sequences.

💡 The constructed tree satisfies the input traversal constraints.

from typing import List, Optional

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

def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if not preorder:
        return None
    root = TreeNode(preorder[0])  # STEP 1
    stack = [root]  # STEP 1
    inorder_index = 0  # STEP 1
    for val in preorder[1:]:  # STEP 2
        node = stack[-1]  # STEP 2
        if node.val != inorder[inorder_index]:  # STEP 3
            node.left = TreeNode(val)  # STEP 3
            stack.append(node.left)  # STEP 3
        else:
            while stack and stack[-1].val == inorder[inorder_index]:  # STEP 6
                node = stack.pop()  # STEP 6
                inorder_index += 1  # STEP 6
            node.right = TreeNode(val)  # STEP 7
            stack.append(node.right)  # STEP 7
    return root  # STEP 9

📊

Construct Tree from Preorder and Inorder - Watch the Algorithm Execute, Step by Step

Watching this step-by-step shows how preorder and inorder sequences guide tree construction, clarifying the stack's role and the order of node attachments.

Current node: 0

3

Current node: 1

39

Current node: 0

39

Current node: 2

3920

Current node: 3

392015

Current node: 2

392015

Current node: 4

3920157

3920157

3920157

Return: 0

3920157

Return: 0

Key Takeaways

✓ The stack tracks nodes whose children are being attached, simulating recursion iteratively.

This insight is hard to see from code alone because the stack's role is implicit; visualization shows how it manages construction order.

✓ Comparing the top of the stack with the current inorder element determines whether to add left children or pop to add right children.

This decision is subtle in code but critical; visualization clarifies how preorder and inorder interplay guides tree shape.

✓ Incrementing inorder_index and popping nodes signals completion of left subtrees and readiness to attach right children.

Understanding when and why nodes are popped is easier when watching the stack state and inorder_index move step-by-step.

Practice

1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Trace dfs on leaf nodes 1 and 2

   Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.

2. Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here

   Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   One camera at root covers all nodes [OK]

Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]

Common Mistakes:

• Counting cameras on leaves instead of parent
• Forgetting to add camera at root if uncovered
• Misinterpreting coverage states

2. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?

easy

A. Postorder traversal using two stacks

B. Level-order traversal using a queue

C. Morris preorder traversal using threaded binary tree

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirement

   The problem requires visiting root before left and right subtrees, which is preorder traversal.

2. Step 2: Identify approach with no extra space

   Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preorder visits root first; Morris traversal achieves this with O(1) space [OK]

Hint: Preorder visits root before children [OK]

Common Mistakes:

• Confusing inorder or postorder with preorder traversal
• Assuming recursion is always needed
• Using level-order which visits nodes by depth

3. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?

easy

A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.

B. Perform a level-order traversal and compare nodes at each level from left to right.

C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.

D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

1. Step 1: Understand the problem requires mirrored subtree comparison

   The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

   The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mirrored recursive DFS matches problem requirements [OK]

Hint: Symmetry requires mirrored subtree comparison [OK]

Common Mistakes:

• Assuming preorder traversal palindrome check works
• Using level-order traversal without mirrored comparison
• Trying brute force subtree permutations

4. What is the time complexity of the optimal countNodes algorithm that uses binary search on the last level of a complete binary tree with n nodes?

medium

A. O(log n)

B. O(n)

C. O((log n)^2)

D. O(n log n)

Solution

1. Step 1: Analyze height and binary search

   Height h = O(log n). Binary search on last level does O(log n) steps.

2. Step 2: Combine existence checks

   Each existence check traverses height h = O(log n). Total time = O(log n) * O(log n) = O((log n)^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested log factors from height and binary search [OK]

Hint: Two nested log factors multiply to (log n)^2 [OK]

Common Mistakes:

• Confusing O(log n) with O((log n)^2)
• Assuming linear time due to traversal

5. What is the time complexity of the parent pointer + ancestor set approach for finding the Lowest Common Ancestor in a binary tree with n nodes and height h?

medium

A. O(h^2) because ancestor set lookups take O(h) each and we do up to h lookups

B. O(n^2) because each node's parent is checked multiple times

C. O(n) to build parent map plus O(h) to find LCA, total O(n)

D. O(n log n) due to sorting ancestors before comparison

Solution

1. Step 1: Identify parent map construction cost

   Building the parent map requires visiting each node once, O(n).

2. Step 2: Analyze ancestor set and LCA search

   Ancestor set insertion and lookup are O(1) average. Traversing up to height h for p and q is O(h). Total is O(n) + O(h) ≈ O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Parent map O(n) + ancestor lookup O(h) = O(n) total [OK]

Hint: Parent map build dominates; ancestor lookup is O(h) [OK]

Common Mistakes:

• Confusing ancestor set lookup as O(h)
• Assuming sorting ancestors needed
• Overestimating repeated parent checks