Binary Tree Cameras - Practice Coding Problems

Binary Tree Cameras - Problem

You are given the root of a binary tree. We install cameras on the tree nodes where 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.

Input & Output

Example 1 — Simple Tree

$ Input: root = [0,0,null,0,0]

› Output: 1

💡 Note: Place one camera at root node 0. It monitors itself and both children at level 1. The grandchildren at level 2 are monitored by their parents.

Example 2 — Single Path

$ Input: root = [0,0,null,0,null,0,null,null,0]

› Output: 2

💡 Note: Two cameras needed - one can be placed optimally to cover 3 nodes each, requiring 2 cameras total for this linear path.

Example 3 — Single Node

$ Input: root = [0]

› Output: 1

💡 Note: Single node tree requires exactly one camera to monitor itself.

Constraints

The number of nodes in the tree is in the range [1, 1000].
Node.val == 0

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes that need monitoring

Camera Coverage

Each camera monitors parent, self, and children

Minimum Cameras

Find optimal placement for full coverage

Key Takeaway

🎯 Key Insight: Use greedy post-order traversal - place cameras only when children need monitoring, ensuring optimal coverage with minimum cameras.

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use greedy post-order DFS with state tracking. Each node has three states: NEED_CAMERA, HAS_CAMERA, or MONITORED. Place cameras only when necessary (when a child needs monitoring). Best approach is Greedy DFS with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy DFS with State Tracking	O(n)	O(h)	Post-order DFS tracking each node's monitoring state
Brute Force - Try All Combinations	O(2^n)	O(n)	Try placing cameras at every possible combination of nodes

Greedy DFS with State Tracking — Algorithm Steps

Define three states: NEED_CAMERA, HAS_CAMERA, MONITORED
Traverse tree in post-order (children first)
Place camera only if child needs monitoring
Update parent state based on children states

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-Order Traversal

Visit children before parent to make optimal decisions

State Management

Track NEED_CAMERA, HAS_CAMERA, MONITORED states

Greedy Placement

Place camera only when a child needs monitoring

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define NEED_CAMERA 0
#define HAS_CAMERA 1
#define MONITORED 2

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int cameras = 0;

int dfs(struct TreeNode* node) {
    if (!node) return MONITORED;
    
    int left = dfs(node->left);
    int right = dfs(node->right);
    
    if (left == NEED_CAMERA || right == NEED_CAMERA) {
        cameras++;
        return HAS_CAMERA;
    }
    
    if (left == HAS_CAMERA || right == HAS_CAMERA) {
        return MONITORED;
    }
    
    return NEED_CAMERA;
}

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

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0 || arr[0] == -1001) return NULL;
    
    struct TreeNode* root = createNode(arr[0]);
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int i = 1;
    
    while (front < rear && i < size) {
        struct TreeNode* node = queue[front++];
        if (i < size && arr[i] != -1001) {
            node->left = createNode(arr[i]);
            queue[rear++] = node->left;
        }
        i++;
        if (i < size && arr[i] != -1001) {
            node->right = createNode(arr[i]);
            queue[rear++] = node->right;
        }
        i++;
    }
    
    return root;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,] \n");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            arr[size] = -1001;
        } else {
            arr[size] = atoi(token);
        }
        size++;
        token = strtok(NULL, "[,] \n");
    }
    
    struct TreeNode* root = buildTree(arr, size);
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in DFS traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

89.5K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy DFS with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler