Rewiring and Pruning

Some problems ask you to change the tree itself: delete nodes that match a rule, cut the tree into a forest, or flatten it into a linked list. The safe way is postorder. Fix the children first, then decide about the node, because a node's situation can change once its children are gone or rewired. Each call reports what the parent needs to finish the job.

The idea#

Rewiring problems break into two families.

Pruning. A node can become deletable only after its children are processed. For example, a node with a target value may not be a leaf until its target-valued leaf children are removed. So each call returns a verdict, "delete me?". The parent nulls the children that said yes and then re-checks itself. Postorder gives you that cascade, where one deletion makes the parent deletable too, at no extra cost.

Splicing. To flatten a tree into a right-pointing list in preorder, a node needs to know where its flattened left part starts and ends. Then it can hang the right part after it. Each call returns (head, tail) of its flattened subtree. The node sets node.right = left_head, left_tail.right = right_head and node.left = None.

The common thread with BST Operations is "report on return": the child's return value tells the parent how to relink.

How to spot it#

The output is the same tree with a different shape, changed in place.

"Delete", "remove", "prune" nodes or leaves that satisfy a condition.
"Return the forest" or "the remaining roots" after deletions.
"Flatten to a linked list", "in place", "convert to a right-skewed tree".
"Invert" or "mirror" the tree.

Template#

The first family, pruning, needs only a yes or no from each child. Each call returns a verdict for its parent. Nodes follow LeetCode's TreeNode(val, left, right).

delete_me(node):                   # postorder verdict for the parent
    if node is None: return True   # nothing here: nulling it is a no-op
    if delete_me(node.left): node.left = None
    if delete_me(node.right): node.right = None
    # children are done, so this node may have just changed
    return whether node now meets the delete rule
return None if delete_me(root) else root

The splice shape#

The second family needs more than a yes or no. Splicing returns both ends of the rebuilt part, so the parent can link through it.

walk(node):                        # returns (head, tail) of the list
    left = walk(node.left) if node.left exists
    right = walk(node.right) if node.right exists
    if left exists:
        node.right = left.head     # node -> left part -> right part
        left.tail.right = right.head, or None
        node.left = None
    tail = tail of the last non-empty part, else node
    return (node, tail)

Pitfalls#

These mistakes miss deletions or lose subtrees.

Pruning in preorder. Deciding about a node before its children are processed misses the cascade, where a parent qualifies only after its children go.
Deleting the root. If the root itself must go, the function must return None (or the new roots), not the old root.
Losing the right subtree while splicing. Save the right part before you overwrite node.right.
Leaving node.left set. A flattened list must have every left pointer cleared.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Delete Leaves With a Given Value

Use the prune template. The delete rule is not node.left and not node.right and node.val == target. A parent with the target value becomes a leaf only after its children go, and postorder catches that.

Hint: Binary Tree Pruning

Same template. A node goes when it has no children left and its value is 0.

Hint: Delete Nodes And Return Forest

Use the same postorder verdict, with a set of values to delete. A deleted node's surviving children become new roots, so add them to the answer before the parent cuts the link. Add the root too if it survives.

Hint: Flatten Binary Tree to Linked List

The splice shape works. A shorter version visits right, then left, then the node (the exact reverse of preorder) and keeps prev, the last node handled. At each node set node.right = prev, node.left = None, prev = node. Walking backward builds the list from tail to head.

Hint: Invert Binary Tree

At each node, swap the left and right children, then recurse into both. Swapping before or after the recursive calls works either way.

Hint: Linking siblings

Populating next pointers is rewiring done level by level. It lives with BFS in Pick the Traversal.

Key takeaways#

Change the shape in postorder: children first, then the node.
Return a verdict ("delete me?") and let the parent cut the link, then re-check itself.
To splice, return both ends of the rebuilt part.
Handle the root separately; it has no parent to cut it off.

Core idea#

Change a tree's shape in postorder. Fix the children first, then decide about the node, because its situation can change once its children are gone. Each call reports what the parent needs to relink.

Key points#

Pruning: each call returns a verdict, "delete me?". The parent nulls the children that said yes, then re-checks itself.
Postorder gives the cascade: a parent can become a leaf only after its children go.
Splicing (flatten): each call returns (head, tail) of its flattened subtree.
Then set node.right = left_head, left_tail.right = right_head and node.left = None.
Shorter flatten: visit right, then left, then the node. Keep prev and set node.right = prev, node.left = None, prev = node.
Forest (delete nodes): a deleted node's surviving children become new roots. Add them before the parent cuts the link.
Same idea as BST operations: the return value tells the parent how to relink.

Template#

delete_me(node):                     # postorder verdict
    if node is None: return True     # nulling it is a no-op
    if delete_me(node.left): node.left = None
    if delete_me(node.right): node.right = None
    # children are done; this node may now be a leaf
    return node is a leaf and node.val == target
return None if delete_me(root) else root

Pitfalls#

Pruning in preorder. It misses the cascade.
Returning the old root when the root itself must go.
Losing the right subtree while you splice. Save it before you overwrite node.right.
Leaving node.left set in a flattened list.

Say it in an interview#

"Children first, then the node, so a parent can re-check itself after its children are removed."
"Each call returns the head and tail of its flattened part."