Bird
Raised Fist0
Interview Preptree-dfshardAmazonGoogle

Binary Tree Cameras

Choose your preparation mode4 modes available
🎯
Binary Tree Cameras
hardTREEAmazonGoogle

Imagine you are installing security cameras in a large building represented as a binary tree. Each camera can monitor its parent, itself, and its immediate children. How do you place the minimum number of cameras to cover every room?

💡 This problem is about placing cameras in a binary tree to cover all nodes with minimum cameras. Beginners often struggle because it requires understanding how to represent node states and use postorder traversal to make optimal greedy decisions, which is not straightforward.
📋
Problem Statement

Given a binary tree, we need to place cameras on some nodes of the tree. Each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree.

The number of nodes in the tree is in the range [1, 10^5].Each node's value is unique (not necessarily required but typical).
💡
Example
Input"[0,0,null,0,0]"
Output1

Place one camera at the node with two children to cover all nodes.

Input"[0,0,null,0,null,0,null,null,0]"
Output2

Two cameras are needed to cover all nodes in this skewed tree.

  • Single node tree → 1 camera needed
  • Complete binary tree with height 1 → 1 camera needed
  • Skewed tree (all left or all right) → cameras placed at alternate nodes
  • Tree with only leaf nodes → cameras needed at parents
⚠️
Common Mistakes
Not using postorder traversal

Cannot correctly determine children's coverage before deciding on current node, leading to incorrect camera placement

✅ Use postorder DFS to process children before parent

Confusing coverage states or mixing them up

Incorrect camera counts or missed coverage

✅ Define clear states (e.g., 0,1,2) and stick to them consistently

Forgetting to add camera if root is not covered after traversal

Root node remains uncovered, failing problem requirements

✅ After DFS, check root state and add camera if needed

Placing cameras on all nodes with uncovered children instead of minimal set

Overcounting cameras, losing optimality

✅ Place camera only on current node if any child is uncovered, not on all uncovered children

Ignoring null nodes coverage

Incorrect base cases cause wrong recursion results

✅ Treat null nodes as covered to simplify logic

🧠
Brute Force (Pure Recursion with All Combinations)
💡 This approach tries all possible ways to place cameras on nodes to cover the entire tree. It is extremely slow but helps understand the problem deeply by exploring all configurations.

Intuition

Try placing a camera or not at each node and recursively check if the entire tree is covered. Return the minimum cameras needed among all valid configurations.

Algorithm

  1. At each node, try placing a camera or not.
  2. Recursively check if the subtree is covered with that choice.
  3. Combine results from left and right subtrees.
  4. Return the minimum cameras needed to cover the entire tree.
💡 The challenge is to check coverage and count cameras for every combination, which leads to exponential complexity.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minCameraCover(root):
    # Returns (covered, cameras) for subtree
    def dfs(node, has_camera, parent_covered):
        if not node:
            return (True, 0)  # Null nodes are covered without cameras

        # Try placing camera here
        left_cam = dfs(node.left, True, True)
        right_cam = dfs(node.right, True, True)
        cameras_with = 1 + left_cam[1] + right_cam[1]

        # Try not placing camera here
        left_no_cam = dfs(node.left, False, has_camera or parent_covered)
        right_no_cam = dfs(node.right, False, has_camera or parent_covered)
        if has_camera or parent_covered:
            cameras_without = left_no_cam[1] + right_no_cam[1]
        else:
            cameras_without = float('inf')

        if cameras_with < cameras_without:
            return (True, cameras_with)
        else:
            return (has_camera or parent_covered, cameras_without)

    covered, cameras = dfs(root, False, False)
    return cameras

# Driver code
if __name__ == '__main__':
    # Build example tree: [0,0,null,0,0]
    root = TreeNode(0)
    root.left = TreeNode(0)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(0)
    print(minCameraCover(root))  # Expected output: 1
Line Notes
def dfs(node, has_camera, parent_covered):Defines recursive function with parameters to track camera placement and coverage
if not node:Base case: null nodes are considered covered without cameras
left_cam = dfs(node.left, True, True)Try placing a camera at current node, so children are covered
cameras_with = 1 + left_cam[1] + right_cam[1]Count cameras if placing camera here
if has_camera or parent_covered:If current node is covered by parent or has camera, no camera needed here
return camerasReturn minimum cameras needed for entire tree
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = dfs(root, false, false);
        return res[1];
    }

    // returns {covered (0 or 1), cameras}
    private int[] dfs(TreeNode node, boolean hasCamera, boolean parentCovered) {
        if (node == null) return new int[]{1, 0};

        int[] leftWithCam = dfs(node.left, true, true);
        int[] rightWithCam = dfs(node.right, true, true);
        int camerasWith = 1 + leftWithCam[1] + rightWithCam[1];

        int[] leftNoCam = dfs(node.left, false, hasCamera || parentCovered);
        int[] rightNoCam = dfs(node.right, false, hasCamera || parentCovered);
        int camerasWithout = (hasCamera || parentCovered) ? leftNoCam[1] + rightNoCam[1] : Integer.MAX_VALUE;

        if (camerasWith < camerasWithout) return new int[]{1, camerasWith};
        else return new int[]{(hasCamera || parentCovered) ? 1 : 0, camerasWithout};
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(0);
        Solution sol = new Solution();
        System.out.println(sol.minCameraCover(root)); // Expected: 1
    }
}
Line Notes
private int[] dfs(TreeNode node, boolean hasCamera, boolean parentCovered)Recursive helper with camera and coverage flags
if (node == null) return new int[]{1, 0};Null nodes are covered with zero cameras
int camerasWith = 1 + leftWithCam[1] + rightWithCam[1];Count cameras if placing camera here
int camerasWithout = (hasCamera || parentCovered) ? ...Calculate cameras if not placing camera here but node covered
return new int[]{1, camerasWith};Return coverage and camera count for placing camera
#include <iostream>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

pair<bool,int> dfs(TreeNode* node, bool hasCamera, bool parentCovered) {
    if (!node) return {true, 0};

    auto leftWithCam = dfs(node->left, true, true);
    auto rightWithCam = dfs(node->right, true, true);
    int camerasWith = 1 + leftWithCam.second + rightWithCam.second;

    auto leftNoCam = dfs(node->left, false, hasCamera || parentCovered);
    auto rightNoCam = dfs(node->right, false, hasCamera || parentCovered);
    int camerasWithout = (hasCamera || parentCovered) ? leftNoCam.second + rightNoCam.second : INT_MAX;

    if (camerasWith < camerasWithout) return {true, camerasWith};
    else return {hasCamera || parentCovered, camerasWithout};
}

int minCameraCover(TreeNode* root) {
    auto res = dfs(root, false, false);
    return res.second;
}

int main() {
    TreeNode* root = new TreeNode(0);
    root->left = new TreeNode(0);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(0);
    cout << minCameraCover(root) << endl; // Expected: 1
    return 0;
}
Line Notes
pair<bool,int> dfs(TreeNode* node, bool hasCamera, bool parentCovered)Recursive function with coverage and camera flags
if (!node) return {true, 0};Null nodes are covered with zero cameras
int camerasWith = 1 + leftWithCam.second + rightWithCam.second;Count cameras if placing camera here
int camerasWithout = (hasCamera || parentCovered) ? ...Calculate cameras if not placing camera here but node covered
return res.second;Return minimum cameras needed for entire tree
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function minCameraCover(root) {
    function dfs(node, hasCamera, parentCovered) {
        if (!node) return [true, 0];

        let leftWithCam = dfs(node.left, true, true);
        let rightWithCam = dfs(node.right, true, true);
        let camerasWith = 1 + leftWithCam[1] + rightWithCam[1];

        let leftNoCam = dfs(node.left, false, hasCamera || parentCovered);
        let rightNoCam = dfs(node.right, false, hasCamera || parentCovered);
        let camerasWithout = (hasCamera || parentCovered) ? leftNoCam[1] + rightNoCam[1] : Infinity;

        if (camerasWith < camerasWithout) return [true, camerasWith];
        else return [hasCamera || parentCovered, camerasWithout];
    }

    let res = dfs(root, false, false);
    return res[1];
}

// Driver code
let root = new TreeNode(0);
root.left = new TreeNode(0);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
console.log(minCameraCover(root)); // Expected: 1
Line Notes
function dfs(node, hasCamera, parentCovered)Recursive helper with camera and coverage flags
if (!node) return [true, 0];Null nodes are covered with zero cameras
let camerasWith = 1 + leftWithCam[1] + rightWithCam[1];Count cameras if placing camera here
let camerasWithout = (hasCamera || parentCovered) ? ...Calculate cameras if not placing camera here but node covered
return res[1];Return minimum cameras needed for entire tree
⏱
Complexity
TimeO(2^n)
SpaceO(n)

At each node, two choices (place camera or not) lead to exponential combinations. The recursion stack can go up to tree height.

💡 For n=20 nodes, this means over a million combinations, which is impractical.
Interview Verdict: TLE

This approach is too slow for large trees but helps understand the problem and motivates optimization.

🧠
Greedy Postorder Traversal with Three States
💡 This approach uses a postorder DFS to assign each node one of three states: has camera, covered without camera, or not covered. It greedily places cameras on children nodes to minimize total cameras.

Intuition

By processing children first, we know if they are covered or not. If any child is not covered, place a camera at current node. If children have cameras, current node is covered. Otherwise, current node is not covered.

Algorithm

  1. Define three states for each node: 0 = not covered, 1 = covered without camera, 2 = has camera.
  2. Traverse the tree postorder (left, right, node).
  3. If any child is not covered (state 0), place a camera at current node (state 2).
  4. If any child has a camera (state 2), current node is covered (state 1).
  5. If children are covered but have no camera, current node is not covered (state 0).
  6. After traversal, if root is not covered, add a camera.
💡 The key is to use postorder so children states are known before deciding on current node, enabling a greedy minimal camera placement.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minCameraCover(root):
    cameras = 0

    # States: 0 = not covered, 1 = covered no camera, 2 = has camera
    def dfs(node):
        nonlocal cameras
        if not node:
            return 1  # Null nodes are covered

        left = dfs(node.left)
        right = dfs(node.right)

        if left == 0 or right == 0:
            cameras += 1
            return 2  # Place camera here

        if left == 2 or right == 2:
            return 1  # Covered by child's camera

        return 0  # Not covered

    if dfs(root) == 0:
        cameras += 1
    return cameras

# Driver code
if __name__ == '__main__':
    root = TreeNode(0)
    root.left = TreeNode(0)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(0)
    print(minCameraCover(root))  # Expected output: 1
Line Notes
cameras = 0Initialize global camera count
def dfs(node):Postorder DFS to determine node state
if not node: return 1Null nodes are considered covered
if left == 0 or right == 0:If any child not covered, place camera here
if dfs(root) == 0:If root not covered after traversal, add camera
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    int cameras = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 0) cameras++;
        return cameras;
    }

    // 0 = not covered, 1 = covered no camera, 2 = has camera
    private int dfs(TreeNode node) {
        if (node == null) return 1;

        int left = dfs(node.left);
        int right = dfs(node.right);

        if (left == 0 || right == 0) {
            cameras++;
            return 2;
        }

        if (left == 2 || right == 2) return 1;

        return 0;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(0);
        Solution sol = new Solution();
        System.out.println(sol.minCameraCover(root)); // Expected: 1
    }
}
Line Notes
int cameras = 0;Global camera count
if (node == null) return 1;Null nodes are covered
if (left == 0 || right == 0)If any child not covered, place camera here
if (left == 2 || right == 2) return 1;Covered if child has camera
if (dfs(root) == 0) cameras++;Add camera if root not covered
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int cameras = 0;

int dfs(TreeNode* node) {
    if (!node) return 1; // covered

    int left = dfs(node->left);
    int right = dfs(node->right);

    if (left == 0 || right == 0) {
        cameras++;
        return 2; // has camera
    }

    if (left == 2 || right == 2) return 1; // covered

    return 0; // not covered
}

int minCameraCover(TreeNode* root) {
    cameras = 0;
    if (dfs(root) == 0) cameras++;
    return cameras;
}

int main() {
    TreeNode* root = new TreeNode(0);
    root->left = new TreeNode(0);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(0);
    cout << minCameraCover(root) << endl; // Expected: 1
    return 0;
}
Line Notes
int cameras = 0;Global camera count
if (!node) return 1;Null nodes are covered
if (left == 0 || right == 0)Place camera if any child not covered
if (left == 2 || right == 2) return 1;Covered if child has camera
if (dfs(root) == 0) cameras++;Add camera if root not covered
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

let cameras = 0;
function dfs(node) {
    if (!node) return 1; // covered

    let left = dfs(node.left);
    let right = dfs(node.right);

    if (left === 0 || right === 0) {
        cameras++;
        return 2; // has camera
    }

    if (left === 2 || right === 2) return 1; // covered

    return 0; // not covered
}

function minCameraCover(root) {
    cameras = 0;
    if (dfs(root) === 0) cameras++;
    return cameras;
}

// Driver code
let root = new TreeNode(0);
root.left = new TreeNode(0);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
console.log(minCameraCover(root)); // Expected: 1
Line Notes
let cameras = 0;Global camera count
if (!node) return 1;Null nodes are covered
if (left === 0 || right === 0)Place camera if any child not covered
if (left === 2 || right === 2) return 1;Covered if child has camera
if (dfs(root) === 0) cameras++;Add camera if root not covered
⏱
Complexity
TimeO(n)
SpaceO(h)

Each node is visited once in postorder. Space is recursion stack up to tree height h.

💡 For n=10^5 and balanced tree, this means about 10^5 operations, which is efficient.
Interview Verdict: Accepted

This is the optimal and standard approach for this problem in interviews.

🧠
Greedy Postorder with Explicit Enum States
💡 This approach is a variant of the previous one but uses explicit named states (e.g., NOT_COVERED, COVERED_NO_CAM, HAS_CAM) for clarity and maintainability.

Intuition

Same as approach 2 but clearer code by defining constants for states, improving readability and reducing bugs.

Algorithm

  1. Define constants for states: NOT_COVERED=0, COVERED_NO_CAM=1, HAS_CAM=2.
  2. Traverse tree postorder.
  3. If any child is NOT_COVERED, place camera at current node.
  4. If any child HAS_CAM, current node is COVERED_NO_CAM.
  5. Otherwise, current node is NOT_COVERED.
  6. Add camera at root if needed.
💡 Explicit states help avoid confusion and make the code self-documenting, which is valuable in interviews.
</>
Code
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

        def dfs(node):
            if not node:
                return COVERED_NO_CAM

            left = dfs(node.left)
            right = dfs(node.right)

            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

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

# 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
Line Notes
NOT_COVERED = 0Define explicit state for uncovered node
COVERED_NO_CAM = 1Define explicit state for covered node without camera
HAS_CAM = 2Define explicit state for node with camera
if left == NOT_COVERED or right == NOT_COVERED:Place camera if any child uncovered
if dfs(root) == NOT_COVERED:Add camera if root uncovered after traversal
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private static final int NOT_COVERED = 0;
    private static final int COVERED_NO_CAM = 1;
    private static final int HAS_CAM = 2;

    private int cameras = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == NOT_COVERED) cameras++;
        return cameras;
    }

    private int dfs(TreeNode node) {
        if (node == null) return COVERED_NO_CAM;

        int left = dfs(node.left);
        int right = dfs(node.right);

        if (left == NOT_COVERED || right == NOT_COVERED) {
            cameras++;
            return HAS_CAM;
        }

        if (left == HAS_CAM || right == HAS_CAM) return COVERED_NO_CAM;

        return NOT_COVERED;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(0);
        Solution sol = new Solution();
        System.out.println(sol.minCameraCover(root)); // Expected: 1
    }
}
Line Notes
private static final int NOT_COVERED = 0;Explicit state for uncovered node
private static final int COVERED_NO_CAM = 1;Explicit state for covered no camera
private static final int HAS_CAM = 2;Explicit state for node with camera
if (left == NOT_COVERED || right == NOT_COVERED)Place camera if any child uncovered
if (dfs(root) == NOT_COVERED) cameras++;Add camera if root uncovered
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

const int NOT_COVERED = 0;
const int COVERED_NO_CAM = 1;
const int HAS_CAM = 2;

int cameras = 0;

int dfs(TreeNode* node) {
    if (!node) return COVERED_NO_CAM;

    int left = dfs(node->left);
    int right = dfs(node->right);

    if (left == NOT_COVERED || right == NOT_COVERED) {
        cameras++;
        return HAS_CAM;
    }

    if (left == HAS_CAM || right == HAS_CAM) return COVERED_NO_CAM;

    return NOT_COVERED;
}

int minCameraCover(TreeNode* root) {
    cameras = 0;
    if (dfs(root) == NOT_COVERED) cameras++;
    return cameras;
}

int main() {
    TreeNode* root = new TreeNode(0);
    root->left = new TreeNode(0);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(0);
    cout << minCameraCover(root) << endl; // Expected: 1
    return 0;
}
Line Notes
const int NOT_COVERED = 0;Explicit uncovered state
const int COVERED_NO_CAM = 1;Explicit covered no camera state
const int HAS_CAM = 2;Explicit has camera state
if (left == NOT_COVERED || right == NOT_COVERED)Place camera if child uncovered
if (dfs(root) == NOT_COVERED) cameras++;Add camera if root uncovered
const NOT_COVERED = 0;
const COVERED_NO_CAM = 1;
const HAS_CAM = 2;

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

let cameras = 0;
function dfs(node) {
    if (!node) return COVERED_NO_CAM;

    let left = dfs(node.left);
    let right = dfs(node.right);

    if (left === NOT_COVERED || right === NOT_COVERED) {
        cameras++;
        return HAS_CAM;
    }

    if (left === HAS_CAM || right === HAS_CAM) return COVERED_NO_CAM;

    return NOT_COVERED;
}

function minCameraCover(root) {
    cameras = 0;
    if (dfs(root) === NOT_COVERED) cameras++;
    return cameras;
}

// Driver code
let root = new TreeNode(0);
root.left = new TreeNode(0);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
console.log(minCameraCover(root)); // Expected: 1
Line Notes
const NOT_COVERED = 0;Explicit uncovered state
const COVERED_NO_CAM = 1;Explicit covered no camera state
const HAS_CAM = 2;Explicit has camera state
if (left === NOT_COVERED || right === NOT_COVERED)Place camera if child uncovered
if (dfs(root) === NOT_COVERED) cameras++;Add camera if root uncovered
⏱
Complexity
TimeO(n)
SpaceO(h)

Same as approach 2, each node visited once, space is recursion stack.

💡 This approach is equally efficient but clearer to read and maintain.
Interview Verdict: Accepted

Preferred approach for clarity and correctness in interviews.

📊
All Approaches - One-Glance Tradeoffs
💡 Approach 2 or 3 is the best to code in interviews due to optimal time and clarity. Approach 1 is only for understanding.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n)Yes (deep recursion)N/AMention only - never code
2. Greedy Postorder TraversalO(n)O(h)Possible but rare in balanced treesYesCode this approach
3. Greedy Postorder with Explicit StatesO(n)O(h)Possible but rareYesPreferred for clarity and maintainability
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding the greedy postorder approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify problem constraints and camera coverage rules.Step 2: Describe brute force approach to show understanding of problem complexity.Step 3: Introduce greedy postorder traversal with three states for optimal solution.Step 4: Code the solution carefully, explaining state meanings.Step 5: Test on examples and edge cases.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 15min → Test: 5min. Total ~35min

What the Interviewer Tests

Ability to model tree states, use DFS postorder traversal, and implement a greedy strategy to minimize cameras.

Common Follow-ups

  • What if cameras can only be placed on leaf nodes? → Requires different strategy, possibly DP.
  • How to extend to n-ary trees? → Similar states and traversal but generalized children handling.
💡 These follow-ups test your ability to adapt the solution to variations and generalizations.
🔍
Pattern Recognition

When to Use

1) Problem involves placing resources on tree nodes to cover others; 2) Coverage depends on parent and children; 3) Minimizing number of placements; 4) Postorder traversal is natural.

Signature Phrases

monitor all nodesminimum number of cameraseach camera covers parent and children

NOT This Pattern When

Problems that require global DP on trees without greedy coverage or that do not involve coverage states.

Similar Problems

Minimum Vertex Cover in a Tree - similar minimal coverage problemMonitor Binary Tree - variant with different coverage rules

Practice

(1/5)
1. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?
easy
A. 4
B. 2
C. 1
D. 3

Solution

  1. Step 1: Initialize variables

    inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
  2. Step 2: First iteration (i=3, node_val=20)

    top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.
  3. Step 3: Second iteration (i=2, node_val=7)

    top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.
  4. Step 4: Third iteration (i=1, node_val=15)

    top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.
  5. Final Answer:

    Option D -> Option D
  6. Quick Check:

    inorder_index decremented twice after popping 7 and 20 [OK]
Hint: inorder_index decrements only when popping matching nodes [OK]
Common Mistakes:
  • Off-by-one error in inorder_index update
  • Confusing when to pop stack
  • Misreading top.val vs inorder[inorder_index]
2. Consider the following code snippet implementing the parent pointer + ancestor set approach for Lowest Common Ancestor. Given the tree below and nodes p=5 and q=1, what is the final returned node's value? Tree structure: 3 / \ 5 1 / \ \ 6 2 8
def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q
easy
A. 3
B. 5
C. 1
D. 2

Solution

  1. Step 1: Trace parent map construction

    Stack starts with root=3. Pop 3, add children 5 and 1 with parent 3. Pop 1, add child 8 with parent 1. Pop 8 (no children). Pop 5, add children 6 and 2 with parent 5. Parent map built for all nodes.
  2. Step 2: Trace ancestor sets and final return

    Ancestors of p=5 are {5,3,None}. For q=1, check if in ancestors: 1 not in {5,3}, move to parent 3 which is in ancestors. Return 3.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Root 3 is LCA of 5 and 1 in given tree [OK]
Hint: LCA of sibling subtrees is their parent [OK]
Common Mistakes:
  • Returning p or q directly
  • Confusing parent pointers
  • Off-by-one in ancestor check
3. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 5: rob_current calculation uses left[0] and right[0]
B. Line 7: Returning (rob_current, not_rob_current)
C. Line 6: not_rob_current uses max(left) + max(right)
D. Line 2: Base case returns (0, 0)

Solution

  1. Step 1: Understand rob_current calculation

    rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.
  2. Step 2: Identify the bug

    Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Using rob values of children overcounts and breaks correctness [OK]
Hint: Rob current node + not_rob children, not rob children [OK]
Common Mistakes:
  • Mixing rob and not_rob indices in tuple
  • Forgetting adjacency constraints
4. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?
def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if current_sum == targetSum:
            res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res
medium
A. Line appending left child to stack
B. Line initializing stack with root node and path
C. Line appending right child to stack
D. Line checking if current_sum == targetSum without verifying leaf node

Solution

  1. Step 1: Identify condition for adding path to results

    Correct code adds path only if current node is leaf and sum matches.
  2. Step 2: Locate bug

    Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Missing leaf check causes incorrect paths in results [OK]
Hint: Always check leaf node before adding path [OK]
Common Mistakes:
  • Adding path before confirming leaf node
  • Forgetting to backtrack in recursion
5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?
hard
A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.
B. Use the brute force approach checking all paths from every node without prefix sums.
C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.
D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

  1. Step 1: Understand path direction relaxation

    Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.
  2. Step 2: Model tree as undirected graph and run DFS from every node

    To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Undirected DFS from every node with prefix sums counts all connected paths [OK]
Hint: Undirected graph DFS needed for arbitrary path directions [OK]
Common Mistakes:
  • Trying to reuse one-directional prefix sum DFS without modification
  • Assuming running DFS twice covers all paths
  • Trying to store both directions in one prefix sum map
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard