This is our solution and implementation to problem #979: Distribute Coins in Binary Tree on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Distribute Coins in Binary Tree on LeetCode.
Problem Analysis
We are given a binary tree of n nodes which hold positive integers or zero, and are told that the sum of the values of the nodes will be n. The integer value corresponds to how many "coins" a particular node has. We must find a way to determine how many times we would need to transfer coins from one node to another in order to have every node contain exactly one coin. A move is defined as transferring a single coin from one node to its parent or child node. In our implementation, we will want to avoid using redundant space or performing multiple iterations over each node.
The diagram below outlines an example input with an outline of how to make the transfers so that each node has a value of 1. Note that:
- in some cases, one or more "source" will appear in a lower depth, or even in a leaf node.
- anytime we make a transfer of a coin, we must count the transfer in the overall count, even if the node receiving it will not itself use the coin, and instead pass it along.
- throughout the process, the number of coins overall will always remain the same.
- if no node has a value of 0, then every node has a value of 1.
Implementation Strategy
We will derive the solution by using depth first traversal to assess the state of each node. We will store two seperate values, one to count the transfers needed on the current branch, and one to count overall. The branch transfers can contain negative values, indicating that certain nodes need coins instead of having a surplus of them. The overall algorithm can be summarized as:
- Keep track of leftBranchCount and rightBranchCount for the current node.
- If there is a left child node, recursively follow these steps for that child.
- If there is a right child node, recurisvely follow these steps for that child.
- Set the branchNumTransfers to leftCount + rightCount + root.val - 1. This will sum up the child transfer values with the current node state. If the current node is a 0, this will subtract from the transfers.
- Add Math.abs(leftBranchCut) + Math.abs(rightBranchCut) to the total number of transfers.
Space and Time Complexity
This has an average space complexity if O(log n), as we will be using the function stack to keep track of our iteration. In the worst case scenario, the space complexity will be O(n). The time complexity is O(n), as we will be visiting each node exactly once.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.