Skip to main content
Talentd

Distribute Coins in Binary Tree - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree14 min readAsked at: Amazon, Microsoft, Goldman Sachs +5
Practice this problem

Problem Statement

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.

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.

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.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Redistribution SimulationO(n^2)O(h)Conceptual understanding of how coins propagate across edges
Post-order Traversal to Calculate Excess CoinsO(n)O(h)Optimal solution for interviews and production; processes each node once

Video Solution

Distribute Coins in Binary Tree - Leetcode 979 - Python • NeetCodeIO • 22,419 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Distribute Coins in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Cameras

Next

Sum of Distances in Tree