Collect Coins In A Tree - Leetcode Solution

The Collect Coins in a Tree problem is a classic graph problem that can be solved efficiently using recursive DFS (deep-first search) traversal. In this problem, we are given a binary tree with n nodes, where each node contains a certain number of coins. We are also given a starting node, and our task is to compute the minimum number of moves required to collect all the coins in the tree. A move is defined as a traversal from one node to an adjacent node in the tree.

To solve this problem, we can perform a bottom-up DFS traversal of the tree and keep track of two values at each node: the number of coins in the current node, and the total number of moves required to collect all the coins in the subtree rooted at this node. We can then use these values to compute the minimum number of moves required for the entire tree.

More specifically, we can define a recursive function called dfs(node), which takes in a node as an argument and returns a tuple containing two values: the total number of coins in the subtree rooted at this node, and the minimum number of moves required to collect all the coins in this subtree. We can then use this function to compute the solution for the entire tree, as shown below:

def dfs(node):
    # base case: if node is empty, return 0 coins and 0 moves
    if not node:
        return (0, 0)
    
    # recursively compute the values for the left and right subtrees
    left_coins, left_moves = dfs(node.left)
    right_coins, right_moves = dfs(node.right)
    
    # compute the total number of coins and moves for this subtree
    total_coins = left_coins + right_coins + node.val
    total_moves = left_moves + right_moves + abs(left_coins - right_coins)
    
    # return the computed values as a tuple
    return (total_coins, total_moves)

# main function to compute the solution for the entire tree
def distributeCoins(root):
    # call the dfs function starting from the root node
    _, moves = dfs(root)
    return moves

In the above code, we first define the dfs function, which takes in a node and recursively computes the values for the left and right subtrees. We then compute the total number of coins and moves for this subtree, using the formulas given in the problem statement. Finally, we return these computed values as a tuple.

In the main distributeCoins function, we simply call the dfs function starting from the root node, and then return the minimum number of moves required for the entire tree.

Overall, this solution has a time complexity of O(n), where n is the number of nodes in the tree, since we perform a single DFS traversal of the entire tree. The space complexity is also O(n), due to the recursion stack used by the DFS traversal.

1