979. Distribute Coins in Binary Tree

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

You are provided with the root of a binary tree, where each node contains a certain number of coins (node.val). The total number of coins in the tree is equal to the total number of nodes (n). Your task is to redistribute the coins so that every node has exactly one coin. Redistribution is done by moving coins between adjacent nodes (where adjacency is defined by the parent-child relationship). On each move, you can take one coin from a node and move it to an adjacent node. This problem asks you to find the minimum number of moves required to achieve a state where every node has exactly one coin.

Intuition

The intuition behind the solution is to use a post-order traversal, which visits the children of a node before visiting the node itself. The number of moves for a single node is the number of excess coins it has or needs. When a node has more coins than it needs (more than 1), the excess can be moved to the parent. Conversely, if it needs coins (has less than 1 coin), it requests coins from its parent.

To compute the number of moves, call the function recursively on the left and right children. The number of moves required for the left subtree is the absolute value of extra/deficit coins in the left subtree and similarly for the right subtree. The current balance of coins for the node is the node's value plus the sum of moves from left and right (which can be positive, negative, or zero) minus one coin that is needed by the node itself. If this balance is positive, it means the node has extra coins to pass up to its parent. If it's negative, it needs coins from its parent. The total number of moves is accumulated in a variable, which is the sum of the absolute values of extra/deficit coins from both subtrees.

This approach works because it ensures that at each level of the tree, we move the minimum necessary coins to balance out the children before considering the parent. This ensures we don't make redundant moves.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The solution uses a depth-first search (DFS) approach to traverse the binary tree and calculate the balance of coins at each node.

Here's a step-by-step walkthrough of the implementation:

  1. Define a nested helper function, dfs, which will perform the DFS traversal. This function accepts a single argument: the current node being visited (initially the root of the tree).

  2. The base case of the recursion is to return 0 if the root passed to the function is None, which means you've reached a leaf node's nonexistent child.

  3. Recursively call dfs on the left child of the current node and store the result in left, which represents the number of excess or deficit coins in the left subtree.

  4. Do the same for the right child and store the result in right.

  5. The main logic of the solution is encapsulated in these two points:

    • The total number of moves required (ans) is increased by abs(left) + abs(right). This represents the total number of moves needed to balance the left and right subtrees of the current node.
    • The dfs function returns left + right + root.val - 1. This return value represents the balance of the current node after accounting for its own coin (root.val), and it's meant to be either passed up to the parent (if positive) or requested from the parent (if negative).

  6. The ans variable is defined in the outer function scope but is modified inside the dfs function. This is done using the nonlocal keyword, which allows the inner function to modify ans that is defined in the non-local (outer) scope.

  7. Initialize ans to 0 before starting the DFS. This variable will accumulate the total number of moves required to balance the tree.

  8. After the DFS completes, ans contains the total number of moves, and the function returns this value.

The algorithm efficiently calculates the required number of moves using a post-order traversal (visit children first, then process the current node), which helps to avoid redundant moves. It does not require any additional data structures beyond the function call stack used for recursion.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's take a simple binary tree as an example to illustrate the solution approach.

Consider this binary tree with 3 nodes:

1    3
2   / \
3  0   0

Here 3, 0, and 0 are the values at each node, respectively, indicating the number of coins they hold. We need to redistribute these coins such that each node has exactly one coin.

  1. Starting at the root, the dfs function is called on the root node which has the value 3.
  2. Since the root is not None, we continue by calling dfs on the left child, which has the value 0.
  3. The left child has no children, so both calls to its children return 0.
  4. Now, the dfs function processes the left child with value 0. Since it needs one coin, the return value of the dfs function will be -1 for this node.
  5. Similarly, dfs is called on the right child, which also has the value 0, and the process is the same as the left child. The return value is -1.
  6. With both children processed, we come back to the root node. We use the return values from the left and right child (-1 from each) to calculate the number of moves required for the root.
  7. The total moves at the root node are abs(-1) + abs(-1) = 2. This is because we need to move one coin to each child.
  8. The current balance for the root node after these moves is 3 + (-1) + (-1) - 1 = 0. Since the root now has exactly 1 coin (which is our goal for every node), it needs no further action.
  9. The ans variable gets updated in each recursive call, and after the entire tree is traversed, it holds the value 2, which is the minimum number of moves required to redistribute the coins.

Finally, after the DFS traversal finishes, we find that the minimum number of moves required for this example is 2.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def distributeCoins(self, root: Optional[TreeNode]) -> int:
10        # Depth-first search (DFS) function to traverse the tree and redistribute coins
11        def dfs(node):
12            # If the current node is None, we do not need to redistribute any coins
13            if node is None:
14                return 0
15              
16            # Recursively redistribute coins for the left and right subtrees
17            left_balance = dfs(node.left)
18            right_balance = dfs(node.right)
19          
20            # Use nonlocal to modify the ans variable declared in the parent function's scope
21            nonlocal moves_count
22            # Increment the total moves by the absolute amount of coins to move from/left child and right child
23            moves_count += abs(left_balance) + abs(right_balance)
24
25            # Return the net balance of coins for the current subtree
26            # Net balance is the coins to be redistributed, i.e., current node's coin plus left and right balance,
27            # and we subtract 1 because the current node should have 1 coin after redistribution
28            return left_balance + right_balance + node.val - 1
29
30        # Initialize the moves counter to 0
31        moves_count = 0
32        # Start DFS from the root to distribute coins and calculate the moves
33        dfs(root)
34        # Return the total number of moves required to distribute the coins
35        return moves_count
36
1// Definition for a binary tree node.
2class TreeNode {
3    int val; // Node's value
4    TreeNode left; // Left child
5    TreeNode right; // Right child
6  
7    // Constructor to create a leaf node.
8    TreeNode(int val) {
9        this.val = val;
10    }
11
12    // Constructor to create a node with specified left and right children.
13    TreeNode(int val, TreeNode left, TreeNode right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21    private int totalMoves; // To track the total number of moves needed
22
23    // Distributes coins in the binary tree such that every node has exactly one coin
24    public int distributeCoins(TreeNode root) {
25        totalMoves = 0; // Initialize the total moves to 0
26        postOrderTraversal(root); // Start post-order traversal from the root
27        return totalMoves; // After traversal, totalMoves has the answer
28    }
29
30    // Helper function to perform post-order traversal of the binary tree
31    private int postOrderTraversal(TreeNode node) {
32        // Base case: if current node is null, return 0 (no moves needed)
33        if (node == null) {
34            return 0;
35        }
36
37        // Recurse on the left subtree
38        int leftMovesRequired = postOrderTraversal(node.left);
39        // Recurse on the right subtree
40        int rightMovesRequired = postOrderTraversal(node.right);
41
42        // Calculate the total moves needed by adding up the moves required by both subtrees
43        totalMoves += Math.abs(leftMovesRequired) + Math.abs(rightMovesRequired);
44
45        // Return the net balance of coins for this node
46        // The net balance is the sum of left and right balances plus the coins at the node minus one (for the node itself)
47        return leftMovesRequired + rightMovesRequired + node.val - 1;
48    }
49}
50
1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructors
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    int distributeCoins(TreeNode* root) {
15        int totalMoves = 0; // This will store the total number of moves needed to balance the coins
16      
17        // The Depth First Search (DFS) function computes the number of moves required
18        // starting from the leaves up to the root of the tree.
19        // It returns the excess number of coins that need to be moved from the current node.
20        function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
21            // Base case: if the current node is null, return 0 since there are no coins to move.
22            if (!node) {
23                return 0;
24            }
25          
26            // Recursive case: solve for left and right subtrees.
27            int leftMoves = dfs(node->left);
28            int rightMoves = dfs(node->right);
29          
30            // The number of moves made at the current node is the sum of absolute values of each subtreeโ€™s excess coins.
31            // Because moves from both left and right need to pass through the current node.
32            totalMoves += abs(leftMoves) + abs(rightMoves);
33          
34            // Return the number of excess coins at this node: positive if there are more coins than nodes,
35            // negative if there are fewer. A value of -1 means just the right amount for the node itself.
36            return leftMoves + rightMoves + node->val - 1;
37        };
38      
39        // Call the DFS function starting from the root of the tree.
40        dfs(root);
41      
42        // Return the total number of moves needed to distribute the coins.
43        return totalMoves;
44    }
45};
46
1// Function to distribute coins in a binary tree to ensure each node has exactly one coin.
2// Each move allows for a coin transfer between a parent and a child node (either direction).
3// The function returns the minimum number of moves needed to achieve this state.
4function distributeCoins(root: TreeNode | null): number {
5    // Variable to keep track of the total number of moves needed.
6    let totalMoves = 0;
7  
8    // Helper function for depth-first search (DFS) to compute the number of moves each subtree needs.
9    function dfs(node: TreeNode | null): number {
10        // If we've reached a null node, return 0 as there are no coins to move.
11        if (!node) {
12            return 0;
13        }
14
15        // Recursively dfs into the left and right subtrees.
16        const leftExcessCoins = dfs(node.left);
17        const rightExcessCoins = dfs(node.right);
18
19        // Add the absolute values of excess coins from left and right subtrees to the totalMoves.
20        // The absolute value is used because it takes the same number of moves whether the coin needs to be moved in or out.
21        totalMoves += Math.abs(leftExcessCoins) + Math.abs(rightExcessCoins);
22      
23        // Return the excess number of coins at this node: positive if there are too many coins, negative if not enough.
24        // Since each node should end up with 1 coin, we subtract 1 from the sum of current node value and excess coins from both children.
25        return leftExcessCoins + rightExcessCoins + node.val - 1;
26    }
27
28    // Start the DFS from the root of the tree.
29    dfs(root);
30
31    // Return the total number of moves calculated using the DFS helper.
32    return totalMoves;
33}
34
Not Sure What to Study? Take the 2-min Quiz๏ผš

Depth first search is equivalent to which of the tree traversal order?

Time and Space Complexity

The given Python code performs a Depth-First Search (DFS) on a binary tree to distribute coins so that every node has exactly one coin.

Time Complexity:

The time complexity of the DFS function is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once during the DFS traversal.

Space Complexity:

The space complexity of the DFS function is O(h), where h is the height of the binary tree. This space is used by the call stack during recursion. In the worst case, if the tree is skewed, the height h can be n, making the space complexity O(n). However, in a balanced binary tree, the space complexity would be O(log n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ