Distribute Coins in Binary Tree

LeetCode 1021 | Difficulty: Medium

Medium

Problem Description

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.

Constraints:

- The number of nodes in the tree is `n`.

- `1 <= n <= 100`

- `0 <= Node.val <= n`

- The sum of all `Node.val` is `n`.

Topics: Tree, Depth-First Search, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 139 ms)

Metric	Value
Runtime	139 ms
Memory	37.7 MB
Date	2022-02-02

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int DistributeCoins(TreeNode root)
{
    int moves = 0;
    DistCoins(root, ref moves);
    return moves;
}

private int DistCoins(TreeNode root, ref int moves)
{
    if (root == null) return 0;
    int left = DistCoins(root.left, ref moves);
    int right = DistCoins(root.right, ref moves);
    moves += (Math.Abs(left)+Math.Abs(right));
    return root.val + left + right -1;;
}
}

📜 1 more C# submission(s)

Submission (2022-02-02) — 141 ms, 38 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int moves = 0;
    public int DistributeCoins(TreeNode root)
    {
        int moves = 0;
    Traverse(root, ref moves);
    return moves;
}

private List<int> Traverse(TreeNode root, ref int moves)
{
    if (root == null) return new List<int> { 0, 0};
    List<int> left = Traverse(root.left, ref moves);
    List<int> right = Traverse(root.right, ref moves);
    moves += (Math.Abs(left[0]-left[1]) + Math.Abs(right[0]-right[1]));
    return new List<int>() {left[0]+right[0]+1, left[1]+right[1]+root.val};
}
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.