The O(n) Club: Distribute Coins in Binary Tree — The DFS Therapy Session

The O(n) Club: Distribute Coins in Binary Tree — The DFS Therapy Session

⚡ TL;DR

Binary tree out of coin balance? Every node needs exactly one coin, but coins are scattered like Monday-morning meetings. You can only pass coins one-by-one between parent and child per move (because reality doesn’t believe in bulk discounts). Your job: the lowest possible total moves.
Brute force? Not unless you hate weekends:

// The rookie approach (don't do this):
public int distributeCoins(TreeNode root) {
    // Simulate every move. Infinite loop, infinite sadness.
    // Real solution: see below!
}

🧠 How Devs Usually Mess This Up

The classic blunder: treating this like a vending machine that dispenses coin showers. Nope—each move pushes one sad little coin along a single parent-child edge. Next, aspiring BFS aficionados try level-order traversals, but pushing coins side-to-side is about as effective as debugging by yelling at a monitor. You can’t brute-force your way out, and you certainly can’t ignore each node’s personal drama—coins must be handled bottom-up, not broadcasted from root like management memes.

🔍 What’s Actually Going On

Imagine every node as an employee on payday: some get too many coins, some get nada, but HR needs equilibrium—with minimal grumbling (aka moves). Think local: each node settles up with its kids before sending coin grievances up the org chart. Post-order DFS is group therapy—fix the little problems first, then the big ones. Each node’s net ‘excess’ is node.val + left + right - 1. Every time coins shuffle across an edge, that’s a move. The real question: how many complaints travel up to HR?

• Process left & right children first (they’re the noisy ones)
• Figure out: is this node short, greedy, or just right?
• Each time a coin leaves or arrives, tally a move
• Pass up the excess (could be positive or negative), let parent worry next

🛠️ PseudoCode

• Handle null nodes: Return 0 (because nulls aren’t greedy, just empty)
• int left = dfs(node.left) — compute net coin drama from the left
• int right = dfs(node.right) — same for right
• Add Math.abs(left) + Math.abs(right) to career moves (the actual answer)
• Return node.val + left + right - 1—what this node passes to parent

Deal with the kids first; your own problems come later. Classic recursion parenting.

💻 The Code

// Java TreeNode definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}
 public class DistributeCoins {
    private int moves = 0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return moves;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        moves += Math.abs(left) + Math.abs(right);
        return node.val + left + right - 1;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Skewed trees (one long branch)—make sure you don’t break when all coins are left or right
• Recall: nulls need nothing; recursion skips them gracefully
• Negative excess? That’s a borrower—still counts as a move when fixed
• Space? Just the call stack: O(height). Time? O(number of nodes). That’s as cheap as recursion therapy gets.

🧠 Interviewer Brain-Tattoo

BFS? Please. When a problem says, “fix it after your kids are done,” it’s screaming for post-order DFS. Remember: the only thing that travels faster than coins in a tree is a bad algorithm to the reject pile.