Binary Tree Cameras

▶

Steps

setup

Initialize cameras count and start DFS at root

Initialize the camera count to zero and begin the DFS traversal at the root node (id=0).

💡 Starting with zero cameras ensures we count only necessary cameras placed during traversal.

Line:

self.cameras = 0
return dfs(root)

💡 The algorithm will explore the entire tree recursively to decide camera placement.

traverse

DFS call on root: move to left child

From root node (id=0), the algorithm calls DFS on its left child (id=1) to explore coverage state.

💡 Postorder traversal requires exploring left subtree before processing current node.

Line:

left = dfs(node.left)

💡 The algorithm defers camera placement decision at root until left subtree is processed.

traverse

DFS call on node 1: move to left child (node 2)

At node 1, DFS calls itself on the left child (node 2) to determine coverage state of that subtree.

💡 Continuing postorder traversal, left subtree of node 1 is explored first.

Line:

left = dfs(node.left)

💡 The algorithm explores the leftmost leaf node first to gather coverage info bottom-up.

traverse

DFS at leaf node 2: left child is null, return COVERED_NO_CAM

Node 2 has no left child, so DFS returns COVERED_NO_CAM (1) for the left subtree.

💡 Null children are considered covered without cameras to simplify coverage logic.

Line:

if not node:
    return COVERED_NO_CAM

💡 Leaves' null children do not require cameras and are treated as covered.

traverse

DFS at leaf node 2: right child is null, return COVERED_NO_CAM

Node 2 has no right child, so DFS returns COVERED_NO_CAM (1) for the right subtree.

💡 Both children of leaf nodes return COVERED_NO_CAM to indicate coverage without cameras.

Line:

right = dfs(node.right)

💡 Leaf nodes have both children covered, so their coverage state depends on their own status.

prune

Determine coverage state of leaf node 2

Since both children are COVERED_NO_CAM and no child is NOT_COVERED, node 2 returns NOT_COVERED (0).

💡 A leaf node with covered children but no camera itself is not covered, signaling need for camera placement above.

Line:

if left == NOT_COVERED or right == NOT_COVERED:
    self.cameras += 1
    return HAS_CAM
if left == HAS_CAM or right == HAS_CAM:
    return COVERED_NO_CAM
return NOT_COVERED

💡 Leaf nodes without cameras are not covered, so parents must consider placing cameras.

traverse

DFS call on node 1: move to right child (node 3)

After processing left child, DFS at node 1 calls itself on right child (node 3) to determine coverage state.

💡 Postorder traversal requires exploring right subtree after left subtree before processing current node.

Line:

right = dfs(node.right)

💡 The algorithm explores the right subtree to gather coverage info before deciding on node 1.

traverse

DFS at leaf node 3: left child is null, return COVERED_NO_CAM

Node 3 has no left child, so DFS returns COVERED_NO_CAM (1) for the left subtree.

💡 Null children are considered covered without cameras to simplify coverage logic.

Line:

if not node:
    return COVERED_NO_CAM

💡 Leaves' null children do not require cameras and are treated as covered.

traverse

DFS at leaf node 3: right child is null, return COVERED_NO_CAM

Node 3 has no right child, so DFS returns COVERED_NO_CAM (1) for the right subtree.

💡 Both children of leaf nodes return COVERED_NO_CAM to indicate coverage without cameras.

Line:

right = dfs(node.right)

💡 Leaf nodes have both children covered, so their coverage state depends on their own status.

prune

Determine coverage state of leaf node 3

Since both children are COVERED_NO_CAM and no child is NOT_COVERED, node 3 returns NOT_COVERED (0).

💡 A leaf node with covered children but no camera itself is not covered, signaling need for camera placement above.

Line:

if left == NOT_COVERED or right == NOT_COVERED:
    self.cameras += 1
    return HAS_CAM
if left == HAS_CAM or right == HAS_CAM:
    return COVERED_NO_CAM
return NOT_COVERED

💡 Leaf nodes without cameras are not covered, so parents must consider placing cameras.

insert

Determine coverage state of node 1 and place camera

Node 1 sees that both children (2 and 3) are NOT_COVERED, so it places a camera here and returns HAS_CAM (2).

💡 Placing a camera at node 1 covers itself and its children, minimizing total cameras.

Line:

if left == NOT_COVERED or right == NOT_COVERED:
    self.cameras += 1
    return HAS_CAM

💡 Cameras are placed greedily at parents of uncovered children to cover maximum nodes.

traverse

DFS call on root: move to right child (null), return COVERED_NO_CAM

Root node's right child is null, so DFS returns COVERED_NO_CAM (1) immediately for the right subtree.

💡 Null children are treated as covered to simplify coverage logic.

Line:

right = dfs(node.right)

💡 Root's right subtree is covered by default since it is null.

prune

Determine coverage state of root node

Root node sees left child HAS_CAM (2), so it returns COVERED_NO_CAM (1) without placing a camera.

💡 If any child has a camera, current node is covered without needing a camera itself.

Line:

if left == HAS_CAM or right == HAS_CAM:
    return COVERED_NO_CAM

💡 Cameras placed at children cover their parents, reducing total cameras needed.

insert

Check if root needs camera after DFS

Since root returned COVERED_NO_CAM (1), no additional camera is added at root.

💡 Only if root is NOT_COVERED would we add a camera here to cover entire tree.

Line:

if dfs(root) == NOT_COVERED:
    self.cameras += 1

💡 Final check ensures root coverage, completing the minimal camera placement.

reconstruct

Return total cameras placed

Return the total number of cameras placed, which is 1, covering all nodes optimally.

💡 The final answer is the minimal number of cameras needed to cover the entire tree.

Line:

return self.cameras

💡 The algorithm successfully minimized cameras by placing one at node 1.

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

NOT_COVERED = 0
COVERED_NO_CAM = 1
HAS_CAM = 2

class Solution:
    def minCameraCover(self, root):
        self.cameras = 0  # STEP 1

        def dfs(node):
            if not node:  # STEP 4,8
                return COVERED_NO_CAM

            left = dfs(node.left)  # STEP 2,3,7
            right = dfs(node.right)  # STEP 9,12

            if left == NOT_COVERED or right == NOT_COVERED:  # STEP 6,11
                self.cameras += 1
                return HAS_CAM

            if left == HAS_CAM or right == HAS_CAM:  # STEP 13
                return COVERED_NO_CAM

            return NOT_COVERED  # STEP 6,10

        if dfs(root) == NOT_COVERED:  # STEP 14
            self.cameras += 1
        return self.cameras  # STEP 15

# Driver code
if __name__ == '__main__':
    root = TreeNode(0)
    root.left = TreeNode(0)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(0)
    sol = Solution()
    print(sol.minCameraCover(root))  # Expected: 1

📊

Binary Tree Cameras - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how decisions to place cameras depend on children's coverage states, which is hard to grasp from code alone.

Current node: 0

0000

DFS Stack

0 (entered)

Current node: 1

0000

DFS Stack

1 (entered)0 (left_done)

Current node: 2

0000

DFS Stack

2 (entered)1 (left_done)0 (left_done)

Current node: 2

0000

DFS Stack

2 (left_done)left=11 (left_done)0 (left_done)

Current node: 2

0000

DFS Stack

2 (right_done)left=1 right=11 (left_done)0 (left_done)

Current node: 2

0000

DFS Stack

1 (left_done)0 (left_done)

Return: 0

Current node: 3

0000

DFS Stack

1 (right_done)left=00 (left_done)

Current node: 3

0000

DFS Stack

3 (left_done)1 (right_done)left=00 (left_done)

Current node: 3

0000

DFS Stack

3 (right_done)left=11 (right_done)left=00 (left_done)

Current node: 3

0000

DFS Stack

1 (right_done)left=0 right=00 (left_done)

Return: 0

Current node: 1

0000

DFS Stack

0 (left_done)left=2

Return: 2

Current node: 0

0000

DFS Stack

0 (right_done)left=2

Current node: 0

0000

DFS Stack

0 (returning)left=2 right=1

Return: 1

0000

0000

Return: 1

Key Takeaways

✓ The algorithm uses a postorder DFS to decide camera placement based on children's coverage states.

This insight is hard to see from code alone because the recursive returns encode coverage states that drive decisions.

✓ Cameras are placed greedily at parents of uncovered children to cover maximum nodes with minimum cameras.

Visualizing the traversal shows how placing cameras at strategic nodes covers multiple nodes efficiently.

✓ The root node may require an additional camera if it remains uncovered after traversal.

This final check is subtle and easy to miss without watching the entire recursion unwind.

Practice

1. You need to determine if a binary tree is height-balanced, meaning the heights of the two child subtrees of any node never differ by more than one. Which approach guarantees an optimal O(n) time solution without redundant height computations?

easy

A. Use a top-down recursive approach that checks balance only at the root node.

B. Compute height for each node separately and check balance at each node recursively.

C. Perform a breadth-first traversal and check balance by comparing subtree sizes at each level.

D. Use a postorder traversal that returns height and balance status simultaneously, stopping early if imbalance is found.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking balance at every node efficiently without recomputing heights multiple times.

2. Step 2: Identify the approach that avoids redundant work

   Postorder traversal that returns both height and balance status in one pass allows early exit on imbalance and avoids repeated height calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Postorder traversal with early exit is O(n) and avoids recomputation [OK]

Hint: Postorder traversal with early exit avoids repeated height calls [OK]

Common Mistakes:

• Checking balance only at root misses subtree imbalances
• Computing height separately for each node causes O(n²) time
• Using BFS to check balance is incorrect as balance depends on subtree heights

2. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 2, 1]

D. [3, 1, 2]

Solution

1. Step 1: Trace traversal on given tree

   Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.

2. Step 2: Process nodes in postorder

   3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches postorder [3, 2, 1] [OK]

Hint: Postorder output for this tree is [3,2,1] [OK]

Common Mistakes:

• Confusing order of appending nodes
• Off-by-one in stack popping

3. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?

easy

A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.

B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.

C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.

D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

1. Step 1: Understand the need for null markers

   Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.

2. Step 2: Recognize BFS with null markers preserves structure

   Level order traversal with null markers records nodes level by level, capturing the exact shape of the tree, enabling correct deserialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Level order with null markers uniquely encodes tree structure [OK]

Hint: Null markers are essential to preserve tree shape [OK]

Common Mistakes:

• Ignoring null markers leads to ambiguous deserialization
• Assuming inorder traversal alone can reconstruct arbitrary trees
• Using greedy or DP approaches that don't preserve structure

4. Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?

def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max_gain(node.left)
        right_gain = max_gain(node.right)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        # Bug: returns sum of both left and right gains to parent
        return node.val + left_gain + right_gain

    max_gain(root)
    return max_sum

medium

A. Line returning 0 for null node

B. Line computing current_path_sum = node.val + left_gain + right_gain

C. Line updating max_sum = max(max_sum, current_path_sum)

D. Line returning node.val + left_gain + right_gain

Solution

1. Step 1: Understand return value meaning

   The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).

2. Step 2: Identify the bug

   Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Return should be node.val + max(left_gain, right_gain) [OK]

Hint: Return value must be single path gain, not sum of both children [OK]

Common Mistakes:

• Returning sum of both children gains
• Ignoring negative gains
• Updating max_sum incorrectly

5. Suppose the binary tree nodes have parent pointers already, but the tree is very deep (height h). You want to find the Lowest Common Ancestor of two nodes p and q. Which approach is best to optimize time and space, and why?

hard

A. Use brute force by checking all ancestors of p and q repeatedly until common ancestor is found.

B. Use the parent pointer + ancestor set approach, building a set for p's ancestors and then traversing q's ancestors.

C. Use recursive DFS from root to find paths to p and q, then compare paths to find LCA.

D. Use the parent pointer + two-pointer technique: move the deeper node up until both nodes are at the same depth, then move both up simultaneously until they meet.

Solution

1. Step 1: Understand problem constraints

   Nodes have parent pointers, tree is deep, so space usage matters.

2. Step 2: Evaluate approaches

   Ancestor set approach (B) uses O(h) space. Recursive DFS (C) and brute force (D) are inefficient for deep trees.

3. Step 3: Two-pointer technique

   Moving deeper node up to equalize depth, then moving both up simultaneously uses O(1) space and O(h) time, optimal for deep trees.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Two-pointer approach optimizes space and time for deep trees with parent pointers [OK]

Hint: Two-pointer approach uses O(1) space for LCA with parent pointers [OK]

Common Mistakes:

• Using ancestor sets unnecessarily
• Recursing from root wasting time
• Brute force repeated ancestor checks