Distribute Coins in Binary Tree solution and explanation
Google
TCS
9 more videos on this problem
Distribute Coins in Binary Tree - Leetcode 979 - PythonNeetCodeIO · 17:41 · 22K views
979. Distribute Coins in Binary Tree | Tricky DFS | RecursionAryan Mittal · 17:24 · 6K views
LeetCode 979. Distribute Coins in Binary Tree Explanation and Solutionhappygirlzt · 8:40 · 2K views
LeetCode 979. Distribute Coins in Binary TreeHappy Coding · 14:48 · 2K views
Leetcode 979 | Distribute Coins in Binary Tree (Java Solution Explained in details)The Tech Granth · 7:35 · 1K views
979. Distribute Coins in Binary Tree (Leetcode Medium)Programming Live with Larry · 29:10 · 1K views
Daily Leetcode #1509: May 18, 2024 - 979. Distribute Coins in Binary TreeProgramming Live with Larry · 13:05 · 650 views
LeetCode 979 Distribute Coins in Binary TreeJeevan Kumar - Cracckify · 7:05 · 639 views
Distribute Coins in Binary Tree (LeetCode 979) (DFS, Preorder Traversal)CodeWithARB · 26:26 · 579 views
Distribute Coins in Binary Tree | Leetcode 979 | Interview Question for DSAMoody Vish · 10:09 · 558 views
The problem
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 <= 1000 <= Node.val <= n- The sum of all
Node.valisn.
Approach overview
Problem Overview: Each node in a binary tree contains some coins, and the total number of coins equals the total number of nodes. The goal is to move coins along edges so every node ends up with exactly one coin while minimizing the number of moves.
Approach 1: Repeated Redistribution Simulation (O(n^2) time, O(h) space)
A straightforward idea is to repeatedly scan the tree and move coins between parents and children whenever a node has more than one coin or zero coins. Each pass attempts to balance local imbalances until every node has exactly one coin. This approach works but becomes inefficient because each redistribution may require multiple full traversals of the tree. In the worst case, every adjustment propagates across many nodes, leading to O(n^2) time complexity with recursion stack space O(h), where h is the tree height. It helps build intuition about coin flow but is rarely used in production or interviews.
Approach 2: Post-order Traversal to Calculate Excess Coins (O(n) time, O(h) space)
The optimal solution performs a post-order traversal of the binary tree. Each recursive call returns the excess coins from that subtree: excess = node.val + left_excess + right_excess - 1. A positive value means the subtree has extra coins to send upward, while a negative value means it needs coins from the parent. The number of moves contributed by a node equals abs(left_excess) + abs(right_excess), because every surplus or deficit must travel across the edge connecting that subtree.
This works because every coin movement corresponds exactly to an imbalance detected during the DFS. By aggregating excess values from children before processing the parent, the algorithm naturally models how coins flow through edges. The traversal touches each node once, giving O(n) time complexity and O(h) recursion space. The technique relies on a classic depth-first search pattern applied to a tree structure.
Recommended for interviews: The post-order DFS approach is the expected solution. Interviewers want to see that you model the problem as a flow of excess coins between subtrees and compute moves during traversal. Mentioning the naive redistribution idea shows problem exploration, but implementing the O(n) DFS solution demonstrates strong tree and recursion fundamentals.
Approach 1: Post-order Traversal to Calculate Excess Coins
To solve the problem, we perform a post-order traversal of the tree. During this traversal, for each node, we calculate the excess coins (i.e., the number of coins - 1) that need to be moved either up to the parent or down to the children. We accumulate the absolute values of excess coins for each move.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def distributeCoins(self, root: TreeNode) -> int:
self.moves = 0
def dfs(node):
if not node:
return 0
left_excess = dfs(node.left)
right_excess = dfs(node.right)
self.moves += abs(left_excess) + abs(right_excess)
return node.val + left_excess + right_excess - 1
dfs(root)
return self.movesclass TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
private int moves = 0;
public int distributeCoins(TreeNode root) {
dfs(root);
return moves;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int leftExcess = dfs(node.left);
int rightExcess = dfs(node.right);
moves += Math.abs(leftExcess) + Math.abs(rightExcess);
return node.val + leftExcess + rightExcess - 1;
}
}#include <cstdlib>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
int moves = 0;
public:
int distributeCoins(TreeNode* root) {
dfs(root);
return moves;
}
int dfs(TreeNode* node) {
if (!node) return 0;
int leftExcess = dfs(node->left);
int rightExcess = dfs(node->right);
moves += abs(leftExcess) + abs(rightExcess);
return node->val + leftExcess + rightExcess - 1;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var distributeCoins = function(root) {
let moves = 0;
function dfs(node) {
if (!node) return 0;
let leftExcess = dfs(node.left);
let rightExcess = dfs(node.right);
moves += Math.abs(leftExcess) + Math.abs(rightExcess);
return node.val + leftExcess + rightExcess - 1;
}
dfs(root);
return moves;
};public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int moves = 0;
public int DistributeCoins(TreeNode root) {
Dfs(root);
return moves;
}
private int Dfs(TreeNode node) {
if (node == null) return 0;
int leftExcess = Dfs(node.left);
int rightExcess = Dfs(node.right);
moves += Math.Abs(leftExcess) + Math.Abs(rightExcess);
return node.val + leftExcess + rightExcess - 1;
}
}This code defines a binary tree node with a value and optional left and right children. The distributeCoins function calculates the minimum number of moves needed to distribute coins such that each node has exactly one coin. The dfs helper function calculates the excess coins at each node using post-order traversal and updates the global count of moves.
Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
Approach 2: DFS
We define a function dfs(node), which represents the coin overload in the subtree rooted at node, i.e., the number of coins minus the number of nodes. If dfs(node) is positive, it means the subtree has more coins than nodes, and the excess coins need to be moved out of the subtree; if dfs(node) is negative, it means the subtree has fewer coins than nodes, and the shortfall needs to be moved into the subtree.
In the function dfs(node), we first traverse the left and right subtrees to obtain the coin overload left and right of the left and right subtrees, respectively. Then, the current number of moves needs to be increased by |left| + |right|, which means moving the coins from the left and right subtrees to the current node. After that, we return the coin overload of the entire subtree, which is left + right + node.val - 1.
Finally, we return the number of moves.
The time complexity is O(n), and the space complexity is O(h). Here, n and h respectively represent the number of nodes and the height of the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function distributeCoins(root: TreeNode | null): number {
let ans = 0;
const dfs = (root: TreeNode | null) => {
if (!root) {
return 0;
}
const left = dfs(root.left);
const right = dfs(root.right);
ans += Math.abs(left) + Math.abs(right);
return left + right + root.val - 1;
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func distributeCoins(root *TreeNode) (ans int) {
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
left, right := dfs(root.Left), dfs(root.Right)
ans += abs(left) + abs(right)
return left + right + root.Val - 1
}
dfs(root)
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Post-order Traversal to Calculate Excess Coins | Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Redistribution Simulation | O(n^2) | O(h) | Conceptual understanding of how coins propagate across edges |
| Post-order Traversal to Calculate Excess Coins | O(n) | O(h) | Optimal solution for interviews and production; processes each node once |
Frequently asked questions
Is Distribute Coins in Binary Tree easy or hard?
Distribute Coins in Binary Tree is typically classified as a Medium difficulty problem. The challenge lies in recognizing that coin movements correspond to subtree excess values and solving it with a post-order DFS rather than simulating individual moves.
Distribute Coins in Binary Tree Python/Java solution
Implement a recursive DFS that returns the excess coins for each subtree. Maintain a global or external counter to accumulate moves using abs(left_excess) + abs(right_excess). The same logic works across Python, Java, C++, C#, and JavaScript implementations.
How to solve Distribute Coins in Binary Tree in O(n)?
Traverse the tree using post-order DFS and compute the excess coins at each node using the formula: node.val + left_excess + right_excess - 1. The absolute values of left_excess and right_excess represent the number of moves required across edges. Summing these values during traversal yields the minimum moves in O(n) time.
What is the best approach for Distribute Coins in Binary Tree?
The best approach uses post-order DFS to compute excess coins from each subtree. For every node, calculate left and right excess values and add their absolute values to the move count. The node returns its remaining excess coins to the parent. This processes the tree once with O(n) time complexity.
Is Distribute Coins in Binary Tree asked at Google/Amazon/Meta?
Binary tree DFS problems like Distribute Coins in Binary Tree frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests recursive reasoning, tree traversal, and the ability to model resource flow across nodes.
What data structure is used in Distribute Coins in Binary Tree?
The problem uses a binary tree data structure combined with a depth-first search traversal. The algorithm relies on post-order traversal so child subtrees are processed before their parent, allowing excess coin values to propagate upward.
What is the time complexity of Distribute Coins in Binary Tree?
The optimal DFS solution runs in O(n) time because each node is visited exactly once during the post-order traversal. At every node, only constant-time calculations are performed. The space complexity is O(h), where h is the height of the tree due to recursion.