Delete Leaves With a Given Value

Medium
1946.

Delete Leaves With a Given Value

Delete Leaves With a Given Value is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

Given the root of a binary tree and an integer target, delete every leaf (a node with no children) whose value is target.

Deleting leaves can turn their parent into a leaf; if that parent's value is also target, it must be deleted too. Keep going until no leaf with value target remains, and return the root of what is left (the empty tree [] if everything was deleted).

Example 1

Input
root = [1,2,3,2,null,2,4], target = 2
Output
[1,null,3,null,4]
Explanation
The leaves 2 go first; that leaves the left 2 a leaf too, so it goes as well. 1, 3 and 4 remain.

Example 2

Input
root = [1,3,3,3,2], target = 3
Output
[1,3,null,null,2]
Explanation
Only the leaf 3 under the left 3 and the right leaf 3 are removed; the left 3 still has the child 2.

Example 3

Input
root = [1,2,null,2,null,2], target = 2
Output
[1]
Explanation
The chain of 2s disappears one leaf at a time, leaving just the root.

Example 4

Input
root = [1,1,1], target = 1
Output
[]
Explanation
Once both leaves go the root is a leaf with the target value, so the whole tree is deleted.

Constraints

  • 1 <= number of nodes <= 3000
  • 1 <= Node.val, target <= 1000
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
 * @param {number} target
 * @return {TreeNode}
 */
var removeLeafNodes = function(root, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Leaves With a Given Value — Problem & Solution

Delete Leaves With a Given Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Delete Leaves With a Given Value is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree and an integer target, delete every leaf (a node with no children) whose value is target.

Deleting leaves can turn their parent into a leaf; if that parent's value is also target, it must be deleted too. Keep going until no leaf with value target remains, and return the root of what is left (the empty tree [] if everything was deleted).

Example 1

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: The leaves 2 go first; that leaves the left 2 a leaf too, so it goes as well. 1, 3 and 4 remain.

Example 2

Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]
Explanation: Only the leaf 3 under the left 3 and the right leaf 3 are removed; the left 3 still has the child 2.

Example 3

Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: The chain of 2s disappears one leaf at a time, leaving just the root.

Example 4

Input: root = [1,1,1], target = 1
Output: []
Explanation: Once both leaves go the root is a leaf with the target value, so the whole tree is deleted.

Constraints

  • 1 <= number of nodes <= 3000
  • 1 <= Node.val, target <= 1000

Hints for Delete Leaves With a Given Value

  1. Hint 1

    Whether a node becomes a removable leaf depends on what happens to its children first.

  2. Hint 2

    So process children before their parent — a post-order walk.

  3. Hint 3

    After pruning both subtrees, if the node now has no children and holds target, return null in its place; otherwise return the node.

How to solve Delete Leaves With a Given Value

A post-order walk settles each subtree before looking at its root, so by the time a node is examined its children have already been deleted if they had to be — one pass does all the cascading.

Approach

  1. If the node is null, return null.
  2. Replace its left child by the result of processing the left subtree, and the same on the right.
  3. If the node now has no children and its value equals target, return null; otherwise return the node.
  4. The value returned for the root is the answer.

Why it works

When the walk returns from a node, that node's subtree contains no leaf equal to target: its children's subtrees were cleaned first, and the node itself is removed exactly when it has become such a leaf. A node that still has a child can never be removed later, because its subtree is final.

Complexity

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

Pitfalls

  • Checking a node before its children (pre-order) misses parents that only become leaves afterwards.
  • The root itself can disappear, giving the empty tree.

Reference solution

Python

from typing import Optional

def removeLeafNodes(root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
    if root is None:
        return None
    root.left = removeLeafNodes(root.left, target)
    root.right = removeLeafNodes(root.right, target)
    if root.left is None and root.right is None and root.val == target:
        return None
    return root

Java

public static TreeNode removeLeafNodes(TreeNode root, int target) {
    if (root == null) return null;
    root.left = removeLeafNodes(root.left, target);
    root.right = removeLeafNodes(root.right, target);
    if (root.left == null && root.right == null && root.val == target) return null;
    return root;
}

C++

TreeNode* removeLeafNodes(TreeNode* root, int target) {
    if (!root) return nullptr;
    root->left = removeLeafNodes(root->left, target);
    root->right = removeLeafNodes(root->right, target);
    if (!root->left && !root->right && root->val == target) return nullptr;
    return root;
}

JavaScript

var removeLeafNodes = function(root, target) {
    if (root === null) return null;
    root.left = removeLeafNodes(root.left, target);
    root.right = removeLeafNodes(root.right, target);
    if (root.left === null && root.right === null && root.val === target) 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