Binary Tree Cameras

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n)	Yes (deep recursion)	N/A	Mention only - never code
2. Greedy Postorder Traversal	O(n)	O(h)	Possible but rare in balanced trees	Yes	Code this approach
3. Greedy Postorder with Explicit States	O(n)	O(h)	Possible but rare	Yes	Preferred 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. Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

Tree structure:
2
/ \ 1 3

from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)  # visit node
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                predecessor.right = None  # remove thread
                result.append(current.val)  # visit node
                current = current.right
    return result

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [2, 1, 3]

D. [3, 2, 1]

Solution

1. Step 1: Trace traversal starting at root=2

   Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.

2. Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).

   Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder traversal of tree 1,2,3 is [1,2,3] [OK]

Hint: Inorder traversal visits left, root, right [OK]

Common Mistakes:

• Appending before removing thread
• Visiting root before left subtree
• Confusing preorder with inorder output

2. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?

easy

A. 5

B. 15

C. 25

D. 26

Solution

1. Step 1: Trace path 1->2

   current_number accumulates 1 then 12; leaf node 2 adds 12 to total.

2. Step 2: Trace path 1->3

   current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.

3. Step 3: Check for off-by-one or missed increments

   Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sum of 12 and 13 is 25, matching code behavior [OK]

Hint: Trace current_number updates carefully at each node [OK]

Common Mistakes:

• Off-by-one in current_number division
• Adding non-leaf nodes to total

3. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?

medium

A. Line creating root node with postorder[-1]

B. Line initializing inorder_index to 0

C. Line attaching node as right child

D. Line popping from stack inside while loop

Solution

1. Step 1: Identify inorder_index initialization

   inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.

2. Step 2: Consequences of wrong initialization

   Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct inorder_index initialization is critical for stack popping logic [OK]

Hint: inorder_index must start at last index, not zero [OK]

Common Mistakes:

• Wrong inorder_index initialization
• Confusing postorder traversal direction
• Incorrect stack popping conditions

4. Suppose the problem is modified so that the tree can have nodes with arbitrary large depth, and you want to avoid recursion stack overflow. Which approach is best to check if the tree is balanced efficiently?

hard

A. Use the brute force recursive height check since it is simpler to implement.

B. Use iterative postorder traversal with a stack to compute heights and check balance.

C. Use a breadth-first traversal and check balance at each level.

D. Use a global variable to store height and recurse with tail recursion optimization.

Solution

1. Step 1: Understand recursion stack limitations

   Deep trees can cause recursion stack overflow in recursive solutions.

2. Step 2: Identify iterative approach benefits

   Iterative postorder traversal uses explicit stack, avoiding recursion limits and still computes heights and balance in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative approach avoids recursion depth issues [OK]

Hint: Iterative traversal avoids recursion stack overflow [OK]

Common Mistakes:

• Assuming recursion with tail call optimization works in Python
• Using BFS which does not check subtree height balance
• Choosing brute force recursion despite stack limits

5. Suppose the problem is modified so that node values can be negative, and you want to find all root-to-leaf paths summing to targetSum. Which modification to the DFS approach is necessary to ensure correctness?

hard

A. Remove pruning and explore all paths fully since negative values can reduce sums

B. Add pruning to stop exploring paths when current_sum exceeds targetSum

C. Use BFS instead of DFS to avoid infinite loops caused by negative values

D. Sort children nodes by value to explore promising paths first

Solution

1. Step 1: Understand effect of negative values

   Negative values can decrease current_sum, so pruning based on exceeding targetSum can miss valid paths.

2. Step 2: Adjust DFS to remove pruning

   To ensure all valid paths are found, pruning must be removed and all paths fully explored.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pruning breaks correctness with negative values; full exploration needed [OK]

Hint: Negative values invalidate pruning based on sum limits [OK]

Common Mistakes:

• Applying pruning blindly
• Switching to BFS unnecessarily