Binary Tree Pruning

Binary Tree Pruning

What is this problem about?

The Binary Tree Pruning coding problem involves removing subtrees that do not contain a specific value (usually '1'). You are given the root of a binary tree where every node's value is either 0 or 1. You need to return the same tree, but "pruned" so that every remaining subtree contains at least one '1'. If a node is a leaf and its value is 0, it should be removed.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask this to test your "bottom-up" recursive thinking. It’s an excellent problem for demonstrating how to use the return value of a recursive call to modify the tree's structure. It requires you to decide whether a node should stay or go based on information gathered from its children, which is a common pattern in tree optimization and garbage collection algorithms.

Algorithmic pattern used

This problem uses a Post-order Traversal (DFS) approach. You recursively call the pruning function on the left and right children first. After the children are processed (and potentially removed), you check if the current node itself has become a leaf (both children are now NULL) and if its value is 0. If both conditions are met, you return NULL to the parent, effectively pruning that node.

Example explanation

Imagine a tree: 1 / 0 1 / \ / 0 0 0 1

1. Look at the left child (0). Its children are both 0. They are pruned.
2. Now the left child (0) is a leaf with value 0. It gets pruned.
3. Look at the right child (1). Its left child is 0 and is a leaf. Pruned. Its right child is 1. Stays.
4. The root (1) now has a NULL left child and a right child (1). It stays. Final tree: Root (1) with only a right child (1), which in turn has a right child (1).

Common mistakes candidates make

A common mistake is trying to prune "top-down." If you check a node before its children, you might miss a 0-node that should be pruned only after its 0-children are removed. Another error is failing to update the parent's left or right pointers with the result of the recursive call, which is necessary to actually detach the pruned nodes.

Interview preparation tip

Whenever a tree problem involves "removing" or "deleting" nodes based on a condition, always consider a post-order traversal. It allows you to make decisions about the parent based on the final state of the children.