Quick Overview

Remove every binary-tree leaf whose value equals a target, repeating as parents turn into matching leaves, and return the possibly empty result in level-order form. It tests reasoning about cascading deletions, correct handling of the root, and edge cases such as matching internal nodes that keep a child.

Repeatedly Delete Leaves Matching a Target Value From a Binary Tree

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Given a binary tree and an integer `target`, delete every leaf whose value equals `target`. Deleting a leaf can turn its parent into a leaf; if that parent's value also equals `target`, it must be deleted as well, and so on, until no leaf with value `target` remains. Return the resulting tree, which is empty if the root itself ends up deleted. ### Function Signature `remove_target_leaves(tree: list[int | None], target: int) -> list[int | None]` ### Tree Encoding The input and the output use the same level-order encoding: - An empty tree is `[]`. - Otherwise the first element is the root's value. Present nodes are then visited in breadth-first order, left to right, and for each one its left child and then its right child are appended, using `None` for an absent child. Children of absent nodes are not listed. - Trailing `None` values are omitted. The input list is always well formed, and the output must be in exactly this canonical form. ### Rules - A leaf is a node with no children. - A node whose value equals `target` but that still has at least one child after all deletions is kept. - Kept nodes never move: every kept node keeps its original parent and its side (left or right). - The returned tree contains no leaf whose value equals `target`. ### Constraints - The input tree has between 1 and 5000 nodes, and its height is at most 500. - Node values and `target` are integers in `[-1000000000, 1000000000]`. ### Examples Input: `tree = [5,7,7,7,3,None,7], target = 7` Output: `[5,7,None,None,3]` The leaf 7 under the root's left child is deleted, but that left child still has the child 3, so it stays. On the right side, deleting the lower 7 turns the root's right child into a leaf with value 7, so it is deleted too. Input: `tree = [3,3,1], target = 3` Output: `[3,None,1]` Only the left leaf is deleted. The root's value is 3, but it still has a child. Input: `tree = [4,4,4], target = 4` Output: `[]`

Overview: Remove every binary-tree leaf whose value equals a target, repeating as parents turn into matching leaves, and return the possibly empty result in level-order form. It tests reasoning about cascading deletions, correct handling of the root, and edge cases such as matching internal nodes that keep a child.

You are given a binary tree encoded as a flat level-order list `tree` and an integer `target`. Delete every leaf whose value equals `target`. Deleting a leaf can turn its parent into a leaf; if that parent's value also equals `target`, it must be deleted as well, and so on, until no leaf with value `target` remains. Return the resulting tree, which is empty if the root itself ends up deleted. ### Tree encoding The input and the output use the same level-order encoding: - An empty tree is `[]`. - Otherwise the first element is the root's value. Present nodes are then visited in breadth-first order, left to right, and for each one its left child and then its right child are appended, using `None` for an absent child. Children of absent nodes are not listed. - Trailing `None` values are omitted. The input list is always well formed, and the returned list must be in exactly this canonical form. ### Rules - A leaf is a node with no children. - A node whose value equals `target` but that still has at least one child after all deletions is kept. - Kept nodes never move: every kept node keeps its original parent and its side (left or right). - The returned tree contains no leaf whose value equals `target`. Because the answer is the canonical encoding of one specific tree, it is unique. ### Examples Example 1 Input: `tree = [5, 7, 7, 7, 3, None, 7]`, `target = 7` Output: `[5, 7, None, None, 3]` The leaf `7` under the root's left child is deleted, but that left child still has the child `3`, so it stays. On the right side, deleting the lower `7` turns the root's right child into a leaf with value `7`, so it is deleted too. Example 2 Input: `tree = [3, 3, 1]`, `target = 3` Output: `[3, None, 1]` Only the left leaf is deleted. The root's value is `3`, but it still has a child. ### Constraints - The input tree has between 1 and 5000 nodes, and its height is at most 500. - Node values and `target` are integers in `[-1000000000, 1000000000]`. - Every value therefore fits in 32-bit signed range; no value can exceed 2^31 - 1, so `int` suffices in Java and C++. In the non-Python languages the absent-child marker is that language's null: `null` inside a JavaScript array, `null` inside `java.util.List<Integer>`, and a valueless `std::optional<int>` inside `std::vector<std::optional<int>>`.

Constraints

  • The input tree has between 1 and 5000 nodes, and its height is at most 500.
  • Node values and target are integers in [-1000000000, 1000000000].
  • The input list is always a well-formed level-order encoding: None marks an absent child of a present node, children of absent nodes are not listed, and trailing None values are omitted.
  • The returned list must use exactly this same canonical encoding, and it contains no leaf whose value equals target.
  • Kept nodes never move: each one keeps its original parent and its side (left or right).
  • All values fit in 32-bit signed range; no value can exceed 2^31 - 1, so int is enough in Java and C++.

Examples

Input: ([5, 7, 7, 7, 3, None, 7], 7)

Expected Output: [5, 7, None, None, 3]

Explanation: Source example 1: the leaf 7 under the left child is deleted but that child keeps the child 3, while on the right the lower 7 goes and turns its parent 7 into a deletable leaf.

Input: ([3, 3, 1], 3)

Expected Output: [3, None, 1]

Explanation: Source example 2: only the left leaf 3 is deleted; the root's value is 3 but it still has the child 1, so it is kept.

Hints

  1. Deleting one leaf can create a new leaf, so decide a node's fate only after everything below it is already settled.
  2. The list is just a serialization: turning it into explicit parent/child links first, and serializing back at the end, keeps the deletion rules separate from the encoding rules.
  3. Re-serializing is where the canonical form matters - an absent child of a present node still occupies a slot, children of absent nodes never do, and trailing None values must be dropped.

Loading coding console...

Show the approach

Approach

Decode the encoding into explicit links, prune bottom-up, then re-encode.

  1. Decode. The first element is the root. Keep a cursor idx = 1 and a queue of the positions of present nodes in breadth-first order; for each dequeued node consume the next two slots as its left child and then its right child, recording a child only when that slot holds a value, and never consuming slots for absent nodes. That reproduces the encoding rule exactly and rebuilds every parent/child link in one linear pass.

  2. Prune. Process the nodes in post-order using an explicit stack (each node is pushed once unexpanded and once expanded), because the height may reach 500 and recursion is unnecessary. Invariant: when a node is finalised, both of its subtrees have already been finalised, so the children that still count are exactly those marked kept. Detach every non-kept child, then mark the node itself not kept if and only if it now has no children and its value equals target. This is literally the cascade in the statement: a parent can only become a deletion candidate after its children are gone, and a single bottom-up pass settles every cascade because a node's status depends only on its own subtree. A node whose value equals target but that retains at least one child is therefore kept.

  3. Re-encode. If the root was not kept, the answer is []. Otherwise emit the root's value and breadth-first traverse the surviving tree, appending two slots for every present node (None for an absent child) and enqueueing only present children; finally strip trailing Nones. Kept nodes keep their original parent and side by construction, since pruning only removes edges pointing at deleted nodes.

Edge cases: a one-node tree equal to target returns [] rather than [None]; a target-valued node with a surviving child stays; interior Nones must be preserved while trailing Nones must be dropped; an all-target chain collapses to the empty tree; target may be absent, zero or negative, and values may sit on either bound of [-1000000000, 1000000000]; the root's value is always present, so a non-empty answer never starts with None.

Time complexity:
O(n), where n is the length of the input encoding: decoding, the post-order pruning pass and the re-encoding each touch every slot a constant number of times.
Space complexity:
O(n) for the child-link arrays, the traversal stack/queue and the output encoding.