Binary Tree Pruning - Practice Coding Problems

Binary Tree Pruning - Problem

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Input & Output

Example 1 — Binary Tree with Mixed Values

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

› Output: [1,null,0,null,1]

💡 Note: The left subtree (null) is already empty. In the right subtree, the node with value 0 at position [1][0] has a left child 0 (no 1s) which gets removed, but keeps the right child 1. Final tree: [1,null,0,null,1]

Example 2 — Complete Removal

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

› Output: [1,null,1,null,1]

💡 Note: Left subtree has only 0s, so it's completely removed. Right subtree keeps the path to the 1. The 0 nodes without 1s in their subtrees are pruned away.

Example 3 — All Zeros Except Root

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

› Output: [1,1,0,1,1,null,1]

💡 Note: Most nodes have value 1 so they're kept. Only the leaf nodes with 0 that don't lead to any 1s are removed.

Constraints

The number of nodes in the tree is in the range [1, 200]
Node.val is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with 0s and 1s: [1,0,1,0,0,0,1]

Identify Subtrees

Find subtrees that contain no 1s (should be removed)

Pruned Result

Tree after removing subtrees: [1,null,1,null,1]

Key Takeaway

🎯 Key Insight: Use post-order traversal to decide about each node after processing its children - keep nodes that have value 1 OR have remaining children

Asked in

f Facebook 25 a Amazon 18 G Google 15

The key insight is to use post-order DFS traversal to process children before making decisions about the current node. A node should be kept only if it has value 1 OR has at least one child remaining after pruning. Best approach is DFS post-order with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Post-Order Traversal	O(n)	O(h)	Use post-order DFS to check children first, then decide about current node
Brute Force - Multiple Tree Traversals	O(n²)	O(h)	For each node, traverse its entire subtree to check if it contains any 1s

DFS Post-Order Traversal — Algorithm Steps

Step 1: Recursively prune left and right subtrees
Step 2: Check if current node has value 1 or any children
Step 3: If neither, return null to remove this node
Step 4: Otherwise, return the node to keep it

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Children

Recursively process left and right children first

Check Current

Check if current node should be kept (has value 1 or children)

Return Result

Return node to keep it, or null to remove it

Code -

solution.c — C

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

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

struct TreeNode* solution(struct TreeNode* root) {
    if (!root) return NULL;
    
    // Post-order: process children first, then current node
    root->left = solution(root->left);
    root->right = solution(root->right);
    
    // Keep node if it has value 1 OR has at least one child
    if (root->val == 1 || root->left || root->right) {
        return root;
    }
    
    // Remove node if it's 0 and has no children
    return NULL;
}

void printTreeArray(struct TreeNode* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    int result[1000];
    bool valid[1000];
    int count = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (node) {
            result[count] = node->val;
            valid[count] = true;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        } else {
            valid[count] = false;
        }
        count++;
    }
    
    while (count > 0 && !valid[count - 1]) {
        count--;
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        if (i > 0) printf(",");
        if (valid[i]) {
            printf("%d", result[i]);
        } else {
            printf("null");
        }
    }
    printf("]\n");
}

int main() {
    // Simplified input parsing for demo
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = malloc(sizeof(struct TreeNode));
    root->left->val = 0;
    root->left->left = malloc(sizeof(struct TreeNode));
    root->left->left->val = 0;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right = malloc(sizeof(struct TreeNode));
    root->left->right->val = 1;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->right = malloc(sizeof(struct TreeNode));
    root->right->val = 1;
    root->right->left = malloc(sizeof(struct TreeNode));
    root->right->left->val = 0;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = malloc(sizeof(struct TreeNode));
    root->right->right->val = 1;
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    
    struct TreeNode* result = solution(root);
    printTreeArray(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in post-order traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

125.0K Views

Medium Frequency

~15 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

DFS Post-Order Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler