Collect Coins in a Tree

Collect Coins in a Tree

What is this problem about?

The Collect Coins in a Tree coding problem is a complex graph problem. You are given a tree where some nodes contain coins. You start at any node and must collect all the coins and return to any node (not necessarily the start). The catch: you can collect a coin if you are within a distance of 2 from the node containing it. You want to find the minimum number of edges you must traverse.

Why is this asked in interviews?

This is a "Hard" problem asked by companies like Uber and Meta. It tests your ability to simplify a complex tree structure by "pruning." It requires identifying that certain parts of the tree (leaves with no coins) are useless, and other parts (nodes near coins) allow you to avoid traversing the entire tree. It evaluates high-level algorithmic thinking and graph reduction techniques.

Algorithmic pattern used

The optimal Tree interview pattern involves Iterative Pruning:

1. Prune empty subtrees: Repeatedly remove leaf nodes that do not contain coins until all leaves have at least one coin.
2. Prune distance-2 nodes: Since you can collect coins from 2 edges away, you can effectively "shave off" two layers of leaf nodes from the remaining tree.
3. Result: The number of edges in the resulting tree multiplied by 2 (since you go back and forth) is the answer.

Example explanation

Imagine a long line of nodes 1-2-3-4-5-6-7 where only 1 and 7 have coins.

1. All nodes are on the path to a coin, so no initial pruning.
2. Shave 1st layer: Remove 1 and 7. New tree: 2-3-4-5-6.
3. Shave 2nd layer: Remove 2 and 6. New tree: 3-4-5.
4. The remaining edges are (3,4) and (4,5). Total 2 edges.
5. Min moves = 2 edges * 2 = 4. Wait, if the tree becomes a single node or empty, the answer is 0.

Common mistakes candidates make

• Complex Traversal: Trying to solve it as a variation of the Traveling Salesperson Problem (TSP) on a tree.
• Wrong Pruning Depth: Not correctly implementing the "distance 2" rule, which requires removing exactly two layers of leaves after the initial coin-less pruning.
• Return to Start: Assuming you must return to the starting node, which might add unnecessary edges.

Interview preparation tip

Pruning is a powerful technique for tree problems. Practice thinking about "What parts of the data can I safely ignore?" before writing any traversal code.