Solving LeetCode 979: Distribute Coins in Binary Tree

LeetCode's daily challenge for today presents a fascinating problem: "Distribute Coins in Binary Tree." The task is to distribute coins in a binary tree so that every node has exactly one coin. In this blog post, we'll explore the problem, explore the solution using Depth-First Search (DFS), and analyze the underlying data structures and time complexity.

Problem Recap: You are given the root of a binary tree with n nodes where each node in the tree contains node.val coins. There are n coins in total throughout the whole tree. In one move, you can move one coin between two adjacent nodes (parent-child relationship). The goal is to return the minimum number of moves required to make every node have exactly one coin.

Solution Approach: The solution employs Depth-First Search (DFS) to traverse the tree and calculate the excess coins at each node. Excess coins are defined as the number of coins in a node plus the excess coins from its children minus one (the coin needed for the node itself). The number of moves is the sum of the absolute values of the excess coins from each node's children.

JavaScript Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val);
 *     this.left = (left===undefined ? null : left);
 *     this.right = (right===undefined ? null : right);
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var distributeCoins = function(root) {
    // Initialize a variable to keep track of the total number of moves
    let moves = 0;

    // Helper function to perform DFS on the tree
    const dfs = (node) => {
        // Base case: if the node is null, return 0 (no excess coins)
        if (node === null) return 0;
        
        // Recursively call dfs on the left and right children
        let leftExcess = dfs(node.left);
        let rightExcess = dfs(node.right);
        
        // Calculate the excess coins for the current node
        // Excess coins = number of coins in the node + excess from left and right subtrees - 1 (for the node itself)
        let excess = node.val + leftExcess + rightExcess - 1;
        
        // The number of moves needed is the absolute value of the excess coins from left and right children
        moves += Math.abs(leftExcess) + Math.abs(rightExcess);
        
        // Return the excess coins for the current node to its parent
        return excess;
    };
    
    // Start DFS traversal from the root
    dfs(root);
    
    // Return the total number of moves needed
    return moves;
};
        

Data Structures: The main data structure used is a binary tree. Each node in the tree has a value representing the number of coins it holds and pointers to its left and right children.

Time Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because each node is visited once during the DFS traversal. The space complexity is O(h), where h is the height of the tree, due to the recursion stack used in DFS.

This problem demonstrates the effectiveness of DFS in traversing trees and calculating values based on the structure's properties. By understanding and leveraging DFS, we can solve complex problems involving tree structures efficiently.

Feel free to reach out with any questions or comments about the solution. Happy coding!