814. Binary Tree Pruning - Solution & Code Guide

The 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.

Example 1:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:

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

Example 3:

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

Constraints:

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

Approach overview

Problem Overview: Given a binary tree containing only 0 and 1, remove every subtree that does not contain a 1. If a subtree is made entirely of zeros, it should be pruned from the parent. The result is a modified tree where every remaining subtree contains at least one 1.

Approach 1: Post-order Traversal (DFS) (Time: O(n), Space: O(h))

The cleanest solution uses post-order traversal with recursion. In post-order, you process the left and right children before evaluating the current node. This order is critical because whether a node should be pruned depends on whether its children contain a 1. Recursively prune the left subtree and assign the result to root.left, then do the same for the right subtree. After both recursive calls return, check the current node: if root.val == 0 and both children are null, the entire subtree contains only zeros and should be removed by returning null.

This approach works because every subtree is evaluated bottom-up. By the time you process a node, its children have already been cleaned. The algorithm visits each node exactly once, giving O(n) time complexity where n is the number of nodes. Recursion depth depends on tree height, so the space complexity is O(h). This method relies on classic Depth-First Search over a Binary Tree, making it both concise and interview-friendly.

Approach 2: Iterative Post-order Traversal (Time: O(n), Space: O(h))

The same pruning logic can be implemented iteratively using an explicit stack to simulate post-order traversal. Maintain a stack of nodes along with a visited flag or use two-stack traversal. The goal is to ensure children are processed before their parent. Once both children of a node have been handled, check whether they were pruned and determine if the current node should also be removed.

This approach avoids recursion and is useful in environments where recursion depth may exceed stack limits. Each node is pushed and popped from the stack at most once, so the total runtime remains O(n). Auxiliary stack space grows with the height of the tree, resulting in O(h) space complexity. The underlying idea is still the same bottom-up evaluation commonly used in Tree dynamic processing problems.

Recommended for interviews: The recursive post-order traversal is the expected solution. It expresses the pruning rule directly: process children first, then decide whether the current node survives. Interviewers typically look for this bottom-up reasoning because it shows you understand how subtree information flows upward. The iterative version demonstrates deeper knowledge of traversal mechanics but is rarely required unless recursion limits are discussed.

Approach 1: Approach 1: Post-order Traversal

This approach uses post-order traversal to traverse each subtree and decide if it should be pruned. Starting from the leaf nodes, it recursively checks if a subtree contains a 1. If a subtree doesn't contain any 1s, it returns null. This way, when the recursion unwinds, only relevant subtrees are kept.

Python

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

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.val == 0 and not root.left and not root.right:
            return None
        return root

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.val == 0 && root.left == null && root.right == null) {
            return null;
        }
        return root;
    }
}

C++

#include <queue>
#include <cmath>

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* pruneTree(TreeNode* root) {
    if (!root) return nullptr;
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (root->val == 0 && !root->left && !root->right) return nullptr;
    return root;
}

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var pruneTree = function(root) {
    if (!root) return null;
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (root.val === 0 && !root.left && !root.right) return null;
    return root;
};

#include <stdlib.h>

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

struct TreeNode* pruneTree(struct TreeNode* root) {
    if (root == NULL) return NULL;
    
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    
    if (root->val == 0 && root->left == NULL && root->right == NULL) {
        free(root);
        return NULL;
    }
    return root;
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode PruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = PruneTree(root.left);
        root.right = PruneTree(root.right);
        if (root.val == 0 && root.left == null && root.right == null) return null;
        return root;
    }
}

The Python solution implements a recursive pruning routine. It performs a post-order traversal by first addressing the left and right subtrees. Nodes rendering left and right subtrees to None and having a value of 0 are also pruned by return of None. This approach ensures robustness in retaining only necessary sections of the tree.

Complexity

Time Complexity: O(N), as every node is processed exactly one time, where N is the total number of nodes in the tree.
Space Complexity: O(H), where H signifies the height of the tree because of the recursive depth.

Try this approach in the editor

Approach 2: Approach 2: Iterative Post-order Traversal

By utilizing an iterative traversal using a stack, the tree can be pruned without recursion. This approach mimics the recursion stack by using an explicit stack to manage nodes that need to be processed. Once the subtree rooted at a node is evaluated, decisions are made to prune or retain nodes based on whether a 1 is found.

Python

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

class Solution:
    def pruneTree(self, root):
        stack = []
        if root: stack.append((root, False))

        prev, state = None, 0

        while stack:
            node, visited = stack[-1]
            if not visited:
                stack[-1] = (node, True)
                if node.right: stack.append((node.right, False))
                if node.left: stack.append((node.left, False))
                continue
            if (not node.left and not node.right and node.val == 0) and stack:
                if node == root:
                    return None
                if prev == node.left:
                    stack[-1][0].left = None
                if prev == node.right:
                    stack[-1][0].right = None

            prev = node
            stack.pop()

        return root.val == 0 and not root.left and not root.right and root is None

Java

import java.util.Stack;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode prev = null;

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if ((node.left == null && node.right == null) || node.left == prev || node.right == prev) {
                if (node.val == 0 && node.left == null && node.right == null) {
                    if (node == root) return null;
                    if (prev == node.left) node.left = null;
                    if (prev == node.right) node.right = null;
                }
                prev = node;
                stack.pop();
            } else {
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            }
        }

        return root.val == 0 && root.left == null && root.right == null ? null : root;
    }
}

C++

#include <stack>
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* pruneTree(TreeNode* root) {
    std::stack<TreeNode*> s;
    if (root) s.push(root);
    TreeNode* prev = nullptr;

    while (!s.empty()) {
        TreeNode* node = s.top();

        if (!node->left && !node->right || node->left == prev || node->right == prev) {
            if (node->val == 0 && (!node->left || node->left == prev) && (!node->right || node->right == prev)) {
                if (prev && prev == node->left) node->left = NULL;
                if (prev && prev == node->right) node->right = NULL;
            }

            prev = node;
            s.pop();
        } else {
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
    }

    return root->val == 0 && !root->left && !root->right ? NULL : root;
}

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var pruneTree = function(root) {
    if (!root) return null;
    let stack = [[root, false]];
    let prev = null;

    while (stack.length > 0) {
        let [node, visited] = stack[stack.length - 1];
        if (!visited) {
            stack[stack.length - 1][1] = true;
            if (node.right) stack.push([node.right, false]);
            if (node.left) stack.push([node.left, false]);
        } else {
            if (node.val === 0 && !node.left && !node.right) {
                if (node === root) return null;
                if (prev && prev === node.left) node.left = null;
                if (prev && prev === node.right) node.right = null;
            }
            prev = node;
            stack.pop();
        }
    }

    return root.val === 0 && !root.left && !root.right ? null : root;
};

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

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

bool containsOne(struct TreeNode* node) {
    if (!node) return false;
    bool leftContains = containsOne(node->left);
    bool rightContains = containsOne(node->right);
    if (!leftContains) node->left = NULL;
    if (!rightContains) node->right = NULL;
    return node->val == 1 || leftContains || rightContains;
}

struct TreeNode* pruneTree(struct TreeNode* root) {
    return containsOne(root) ? root : NULL;
}

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode PruneTree(TreeNode root) {
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        TreeNode prev = null;

        while (stack.Count > 0) {
            TreeNode node = stack.Peek();
            if ((node.left == null && node.right == null) || node.left == prev || node.right == prev) {
                if (node.val == 0 && node.left == null && node.right == null) {
                    if (node == root) return null;
                    if (prev == node.left) node.left = null;
                    if (prev == node.right) node.right = null;
                }
                prev = node;
                stack.Pop();
            } else {
                if (node.right != null) stack.Push(node.right);
                if (node.left != null) stack.Push(node.left);
            }
        }

        return root.val == 0 && root.left == null && root.right == null ? null : root;
    }
}

Employing manual stack management, this Python implementation executes an iterative approach to pruning, circumventing recursive call overheads. Nodes are investigated post-order, determining prunability by contextual subtree status, assuring comprehensive solution application.

Complexity

Time Complexity: O(N), seeing as nodes must be reviewed.
Space Complexity: O(N), reflecting stack utility and consequent space overheads.

Try this approach in the editor

Approach 3: Recursion

First, we check if the current node is null. If it is, we directly return the null node.

Otherwise, we recursively prune the left and right subtrees and reassign the pruned subtrees to the current node's left and right children. Then, we check if the current node's value is 0 and both its left and right children are null. If so, we return the null node; otherwise, we return the current node.

Time complexity is O(n), and space complexity is O(n). Here, n is the number of nodes in the binary tree.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pruneTree(root: TreeNode | null): TreeNode | null {
    if (!root) {
        return root;
    }
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (root.val === 0 && root.left === root.right) {
        return null;
    }
    return root;
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pruneTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left = pruneTree(root.Left)
	root.Right = pruneTree(root.Right)
	if root.Val == 0 && root.Left == nil && root.Right == nil {
		return nil
	}
	return root
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn prune_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if root.is_none() {
            return None;
        }

        let root = root.unwrap();
        let left = Self::prune_tree(root.borrow_mut().left.take());
        let right = Self::prune_tree(root.borrow_mut().right.take());
        if root.borrow().val == 0 && left.is_none() && right.is_none() {
            return None;
        }

        root.borrow_mut().left = left;
        root.borrow_mut().right = right;
        Some(root)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Post-order Traversal	Time Complexity: O(N), as every node is processed exactly one time, where N is the total number of nodes in the tree. Space Complexity: O(H), where H signifies the height of the tree because of the recursive depth.
Approach 2: Iterative Post-order Traversal	Time Complexity: O(N), seeing as nodes must be reviewed. Space Complexity: O(N), reflecting stack utility and consequent space overheads.
Recursion	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Post-order Traversal	O(n)	O(h)	Best general solution. Clean recursive logic and commonly expected in interviews.
Iterative Post-order Traversal	O(n)	O(h)	Useful when recursion depth may be large or recursion is restricted.

Frequently asked questions

Is Binary Tree Pruning easy or hard?

Binary Tree Pruning is considered a medium-level problem. The main challenge is recognizing that post-order traversal is required because pruning decisions depend on the results from child subtrees.

How to solve Binary Tree Pruning in O(n)?

Use a post-order depth-first traversal. Recursively process the left and right subtrees first, assigning the returned nodes back to root.left and root.right. After both calls, remove the current node if its value is 0 and both children are null. Each node is processed once, giving O(n) time complexity.

Binary Tree Pruning Python or Java solution?

Both Python and Java solutions typically implement recursive post-order traversal. The function processes left and right children, prunes subtrees returning null when needed, and returns the cleaned node. The logic is identical across languages with O(n) time complexity.

What is the best approach for Binary Tree Pruning?

The best approach is post-order traversal using depth-first search. By processing the left and right children before the current node, you can determine whether a subtree contains a 1. If both children are null and the node value is 0, the subtree is pruned. This approach runs in O(n) time and O(h) space where h is the tree height.

Is Binary Tree Pruning asked at Google/Amazon/Meta?

Binary tree pruning problems appear in variations across major tech interviews, including companies like Amazon, Google, and Meta. Interviewers use it to test tree traversal knowledge, recursion, and bottom-up reasoning with depth-first search.

What data structure is used in Binary Tree Pruning?

The problem uses a binary tree as the primary data structure and depth-first search for traversal. The recursive solution relies on the call stack, while the iterative approach uses an explicit stack to simulate post-order traversal.

What is the time complexity of Binary Tree Pruning?

Binary Tree Pruning runs in O(n) time because every node in the tree is visited exactly once during traversal. The algorithm checks the children and potentially removes a node after processing its subtree. Space complexity is O(h) due to recursion stack or the iterative traversal stack, where h is the height of the tree.

Binary Tree Pruning solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Post-order Traversal

Approach 2: Approach 2: Iterative Post-order Traversal

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Binary Tree Pruning solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Post-order Traversal

Approach 2: Approach 2: Iterative Post-order Traversal

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems