Binary Tree Pruning

Medium
1930.

Binary Tree Pruning

Binary Tree Pruning is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

You are given the root of a binary tree in which every node holds 0 or 1. Remove every subtree that does not contain a 1, and return the root of what remains (an empty tree if nothing does).

The subtree of a node is the node together with all of its descendants.

Example 1

Input
root = [1,null,0,0,1]
Output
[1,null,0,null,1]
Explanation
The left child of the 0 is a lone 0 and is removed; the 0 itself stays because its subtree contains a 1.

Example 2

Input
root = [1,0,1,0,0,0,1]
Output
[1,null,1,null,1]
Explanation
The whole left subtree is zeros and goes; on the right only the path down to the last 1 survives.

Example 3

Input
root = [0,0,0]
Output
[]
Explanation
No node holds a 1, so the entire tree is pruned away.

Constraints

  • The number of nodes in the tree is in the range [1, 200]
  • Node.val is either 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Pruning — Solution in Python, Java & C++

Binary Tree Pruning solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Tree Pruning is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given the root of a binary tree in which every node holds 0 or 1. Remove every subtree that does not contain a 1, and return the root of what remains (an empty tree if nothing does).

The subtree of a node is the node together with all of its descendants.

Example 1

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: The left child of the 0 is a lone 0 and is removed; the 0 itself stays because its subtree contains a 1.

Example 2

Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
Explanation: The whole left subtree is zeros and goes; on the right only the path down to the last 1 survives.

Example 3

Input: root = [0,0,0]
Output: []
Explanation: No node holds a 1, so the entire tree is pruned away.

Constraints

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

Hints for Binary Tree Pruning

  1. Hint 1

    Whether a node survives depends on its subtree — so decide for the children before deciding for the node.

  2. Hint 2

    Prune both children recursively first. Afterwards, a node with no remaining children survives only if it holds 1.

  3. Hint 3

    Return null for a pruned subtree and assign the results back to left and right; the root itself can disappear.

How to solve Binary Tree Pruning

A post-order walk prunes the children first; then a node is removable exactly when both its pruned children are empty and its own value is 0.

Approach

  1. prune(node): return null for null.
  2. Set node.left = prune(node.left) and node.right = prune(node.right).
  3. If both are now null and node.val == 0, return null; otherwise return node.
  4. The answer is prune(root).

Why it works

After pruning, a child subtree is non-empty exactly when it contains a 1 (by induction from the leaves). So a node's whole subtree lacks a 1 precisely when both pruned children are empty and the node is 0 — the case that returns null.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Checking the node before pruning its children misses zero-leaves whose removal turns their parent into a removable zero-leaf.
  • The root itself may be pruned — the result can be empty.

Reference solution

Python

from typing import Optional

def pruneTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if root.left is None and root.right is None and root.val == 0:
        return None
    return root

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals