Delete Leaves With a Given Value

NeetCode: Delete Leaves With a Given Value · LeetCode: 1325. Delete Leaves With a Given Value · Difficulty: Medium

Given a binary tree and an integer target, delete all leaf nodes whose value equals target. Deleting a leaf may turn its parent into a leaf; if that parent also has value target, it must be deleted too. Keep going until no such leaf remains, and return the resulting tree.

Example

Text

Input:  root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]

Input:  root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

In the first example the leaves 2 (under the first 2) and 2 (under 3) go first; then the first 2 becomes a leaf and goes too.

The programs print the result in preorder with N for a missing child.

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Deleting a node means returning null in its place: the parent stores the returned reference, so the node is no longer reachable and the garbage collector reclaims it.

Brute force: repeat passes until nothing changes

One pass removes every leaf equal to target that exists at the start. Removing them can expose new leaves, so run passes until a pass deletes nothing. Each pass is a full traversal, and a pass may peel off only one layer (for a chain of target values, one node per pass), so the worst case is n passes of O(n).

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private boolean changed;

    // Removes the leaves that are target-valued right now (one layer).
    private TreeNode onePass(TreeNode node, int target) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null && node.val == target) {
            changed = true;
            return null;
        }
        node.left = onePass(node.left, target);
        node.right = onePass(node.right, target);
        return node;
    }

    public TreeNode removeLeafNodes(TreeNode root, int target) {
        do {
            changed = false;
            root = onePass(root, target);
        } while (changed);
        return root;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    static String serialize(TreeNode root) {
        if (root == null) {
            return "N";
        }
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(serialize(s.removeLeafNodes(tree(1, 2, 3, 2, null, 2, 4), 2)));
        System.out.println(serialize(s.removeLeafNodes(tree(1, 3, 3, 3, 2), 3)));
        System.out.println(serialize(s.removeLeafNodes(tree(1, 1, 1), 1)));
    }
}

Output

1,N,3,N,4,N,N
1,3,N,2,N,N,N
N

onePass deletes a leaf and returns without rechecking the parent, so a parent is examined only in the next pass; the number of passes grows with depth. Time: O(n * h), so O(n^2) on a chain. Space: O(h) recursion.

Optimal: one post-order pass

A node becomes a deletable leaf only after its children have been dealt with, so decide about a node after processing its subtrees. Recurse into the left and right children first (replacing each child with the returned result), and then, if the node is now a leaf with value target, return null; otherwise return the node. Post-order handles the cascade in a single traversal: a parent sees the already-pruned children.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public 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;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    static String serialize(TreeNode root) {
        if (root == null) {
            return "N";
        }
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(serialize(s.removeLeafNodes(tree(1, 2, 3, 2, null, 2, 4), 2)));
        System.out.println(serialize(s.removeLeafNodes(tree(1, 3, 3, 3, 2), 3)));
        System.out.println(serialize(s.removeLeafNodes(tree(1, 1, 1), 1)));
    }
}

Output

1,N,3,N,4,N,N
1,3,N,2,N,N,N
N

Time: O(n). Space: O(h) for the recursion.

Interview points

A deletion can expose a new leaf, so the decision about a node comes after its children are processed.
Returning the (possibly null) node and assigning it to the parent's field is the standard way to delete from a tree.
Repeated passes cost O(n * h); a single post-order pass costs O(n).

Summary

Post-order: process children, then decide about the node.
Time O(n), space O(h).
The root itself can be deleted, so the method returns the new root.