Post-order deletion / pruning
Decide at the parent after the children report; a deleted node promotes its children.
A subtree is returned pruned, so the parent only looks at its own two children.
01The intuition
Start with what you would do by hand
A tree: 1 at the top; 2 and 3 below; 4 and 5 under 2; 6 and 7 under 3. Delete the nodes 3 and 5. When a node goes, its children do not vanish; they become the tops of their own little trees. The result is a forest: the tree under 1 (now 1, 2, 4), the tree 6, and the tree 7.
By hand, you would cross out 3 and 5, then look at every remaining node and ask "is my parent crossed out, or do I have no parent?"; if so, I am a root. This needs parent pointers, which binary tree nodes usually do not have. Doing it from the top down also has a trap: if you remove 3 from its parent first, you lose your only way of reaching 6 and 7.
Build the structure, one piece at a time
The tree is unchanged; the structure we add is a set of values to delete, for O(1) membership checks, and a list of forest roots.
Piece one: handle children before the parent. Visit a node, first recurse into its left and right subtrees, and only then decide about the node itself. Each recursive call returns what should hang in that position afterwards: the same node, or nothing if it was deleted.
Piece two: deciding at the node. After the children have returned, reattach them: left = whatever the left call returned, right = whatever the right call returned. If this node is in the delete set, its surviving children have no live parent, so add each of them to the forest list, and return nothing to the parent. If it is not deleted, return the node.
Piece three: the top. Whatever the root call returns, if it is not nothing, is also a forest root.
| Finish visiting | Deleted? | Returns to parent | Added to forest |
|---|---|---|---|
| 4 | no | 4 | |
| 5 | yes | nothing | (no children) |
| 2 | no | 2, now with right = nothing | |
| 6 | no | 6 | |
| 7 | no | 7 | |
| 3 | yes | nothing | 6, 7 |
| 1 | no | 1, now with right = nothing | 1 (top of tree) |
Why it is correct
The invariant: a recursive call returns its subtree already pruned, with every deleted node removed and every orphan already recorded. Leaves satisfy it trivially. If both children's calls satisfy it, then after reattaching, the only node not yet decided is this one, and we decide it by one set lookup. So the parent never has to look deeper than its own two children, and the top call returns the fully pruned tree.
A node becomes a forest root exactly when it survives and its parent does not (or it has no parent). We add children at the moment their parent is deleted, which is the only moment both facts are known together, and the top of the tree is handled separately.
roots = { v : v survives and (parent(v) is deleted or v is the root) }
Why it is fast
Every node is visited once, does one set lookup and at most two reattachments: O(n) time, plus the set of size k and the recursion stack of O(h). The by-hand method needed parent pointers and a second scan; this does it in one walk.
How to recognise it in an interview
"Delete these nodes and return the remaining trees", "remove every subtree that contains no 1", "delete leaves with a given value, repeatedly", "trim the tree to a range". The shared shape is a decision at a node that depends on what its children became. Say: "I will recurse post-order, let each call return the pruned subtree, and decide about the node after reattaching the children." Delete Nodes And Return Forest is this exactly. Binary Tree Pruning returns nothing for a subtree that ends up with no 1 in it. Delete Leaves With a Given Value works because a node that becomes a leaf after its children are deleted is judged after them.
02The idea in one line
Decide at the parent after the children report; a deleted node promotes its children.
Reach for it when: Delete nodes and return forest, prune tree, delete leaves with value, trim BST.
Cost: O(n) time.
03The walk-through, step by step
The video works one example: Delete Nodes [3,5] from [1,2,3,4,5,6,7]. These are its captions in order, so you can follow without the video or check a step you missed.
- Delete 3 and 5; every orphaned child becomes a new root
- Visit 1, go down first
- Visit 2, go down first
- Visit 4, go down first
- 4 stays attached to its parent
- Visit 5, go down first
- 5 is deleted: cut it out, its children already reported
- 2 stays attached to its parent
- Visit 3, go down first
- Visit 6, go down first
- 6 survives with no live parent: it is a forest root
- Visit 7, go down first
- 7 survives with no live parent: it is a forest root
- 3 is deleted: cut it out, its children already reported
- 1 survives with no live parent: it is a forest root
- Forest: roots 1, 6, 7; the nodes 3 and 5 are gone
- One post-order pass: O(n)
04Asked at Google
6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Delete Nodes And Return Forest | Medium | 37 | last 6 months |
| Height of Binary Tree After Subtree Removal Queries | Hard | 27 | |
| Find Leaves of Binary Tree | Medium | 24 | last 6 months |
| Delete Leaves With a Given Value | Medium | 11 | |
| Trim a Binary Search Tree | Medium | 8 | |
| Binary Tree Pruning | Medium | 5 |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.