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.

Description Solution Video 17:41

979. Distribute Coins in Binary Tree

Medium77.2% acceptance8 companies

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: