Jobs

Interviews

Discussions

Distribute Coins in Binary Tree

Medium

Distribute Coins in Binary Tree

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the coins in each node, and can the number of coins in a node be negative?
Can the tree be empty or contain null nodes, and if so, how should I handle those cases?
Does the tree have to be a complete or balanced binary tree, or can it be arbitrarily shaped?
Are we only concerned with the *minimum* number of moves required to distribute the coins?
If a node has excess coins, can those coins be directly transferred to its descendants (grandchildren, etc.) or only to its immediate children?

Brute Force Solution

Approach

Imagine each part of the tree (each node) is like a person who either needs coins or has too many. The brute force approach is to try every possible way of moving coins around until everyone has exactly one coin.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Look at each connection between two people (nodes) and consider every possible number of coins we could move across that connection.
For each choice of coin movements, check if that movement makes things better for everyone involved: does it bring each person closer to having exactly one coin?
Continue exploring different coin movements, going down the tree to each person (node) and trying out various amounts of coins to shift.
Keep track of how many coin movements it takes for each different way of moving coins around.
At the end, pick the way that took the fewest total coin movements. That is our best answer.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def distribute_coins_brute_force(root):
    min_moves = float('inf')

    def calculate_moves(node, moves):
        nonlocal min_moves

        if not node:
            return 0

        # Recursively process left and right subtrees.
        left_coins = calculate_moves(node.left, moves)
        right_coins = calculate_moves(node.right, moves)

        coins_needed = 1 - node.value

        total_coins_to_redistribute = left_coins + right_coins + node.value
        
        # If the current node is None, it contributes zero coins and zero moves
        if node is None:
            return 0

        # Explore all possible coin distributions.
        if node.left:
            moves += abs(left_coins)

        if node.right:
            moves += abs(right_coins)

        if not node.left and not node.right:
            return node.value - 1

        coins_at_node = node.value + left_coins + right_coins
        coins_to_pass_up = coins_at_node - 1

        # If all nodes have been visited, update the minimum moves.
        if not root.left and not root.right:
            min_moves = min(min_moves, moves)

        return coins_to_pass_up

    total_moves = 0
    calculate_moves(root, total_moves)

    return int(min_moves)

Big(O) Analysis

Time Complexity

O(k^n) – The provided brute force approach explores every possible coin distribution across the binary tree. For a tree with n nodes, each node can potentially send or receive coins. Let's assume each node can have up to k coins (where k depends on the initial coin distribution and tree structure). The algorithm essentially explores all possible combinations of coin movements between nodes. This leads to a search space where each of the n nodes can have k different states, resulting in k^n possible configurations. Therefore, the time complexity grows exponentially with the number of nodes.

Space Complexity

O(N) – The brute force approach explores all possible coin movements through recursive calls. In the worst-case scenario, where the tree is highly skewed (e.g., a linked list), the depth of the recursion can reach N, where N is the number of nodes in the tree. Each recursive call adds a new frame to the call stack, storing information about the current node and coin movements. Therefore, the auxiliary space complexity is proportional to the maximum depth of the recursion, which is O(N).

Optimal Solution

Approach

The core idea is to think about how many coins each part of the tree needs to either give or receive. We move coins around the tree, counting the number of moves needed to balance everything out. We handle this efficiently by solving smaller sub-problems (the subtrees) and combining their results to solve the bigger problem.

Here's how the algorithm would work step-by-step:

Imagine each part of the tree (each node) either needs coins or has extra coins.
Start at the bottom of the tree (the leaves) and work your way up.
For each part, figure out if it needs coins from its parent or can give coins to its parent.
The number of coins sent up or requested is how far out of balance that part of the tree is.
Keep track of the number of coins that had to be moved (this is the number of moves).
The total number of moves needed to balance the whole tree is the answer.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def distribute_coins(root):
    number_of_moves = 0

    def dfs(node):
        nonlocal number_of_moves

        if not node:
            return 0

        # Recursively calculate the balance for the left and right subtrees.
        left_subtree_balance = dfs(node.left)
        right_subtree_balance = dfs(node.right)

        #The number of moves is incremented by the absolute value of the balance
        number_of_moves += abs(left_subtree_balance) + abs(right_subtree_balance)

        # Return the balance of the current node to its parent.
        # Balance is the excess coins at node and subtrees - 1 coin for node.
        return node.val + left_subtree_balance + right_subtree_balance - 1

    dfs(root)
    return number_of_moves

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a depth-first traversal of the binary tree, visiting each node exactly once. At each node, it performs a constant amount of work to calculate the excess coins and update the move count. Since the number of nodes in the tree is 'n', where n is the input size, the algorithm's runtime is directly proportional to n. Therefore, the time complexity is O(n).

Space Complexity

O(H) – The dominant factor for space complexity is the recursion stack. The function recursively calls itself on the left and right children of each node. In the worst-case scenario, the binary tree is skewed, resembling a linked list, leading to a recursion depth proportional to the height (H) of the tree. Therefore, the space used by the recursion stack is O(H), where H can be N in the worst case, and logN in the best (balanced tree) or average case. The plain English description highlights recursively solving subtrees, indicating the use of the call stack.

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 if the root is null as no moves are needed.
Single node tree	Return 0 because a single node tree will always be balanced.
Tree with all nodes having 1 coin	The algorithm correctly calculates 0 moves since the tree is already balanced.
Tree with coins concentrated on one side (highly skewed)	The recursive nature of the solution correctly propagates deficits/surpluses and calculates moves for each subtree.
Tree with maximum allowable nodes (large N)	Ensure the recursion depth doesn't exceed allowable limits, and that integer overflow doesn't occur in the coin counts.
Node values near Integer.MAX_VALUE or Integer.MIN_VALUE	Use long to avoid integer overflow when calculating the balance at each node and when adding the moves.
Unbalanced tree structure, deep on one side	Recursive algorithm handles unbalanced trees as it visits each node, calculating the coins moved in each subtree.
Tree where total coins does not equal the total nodes	The algorithm should still correctly compute the minimum moves required to distribute the existing coins; it does not need to handle cases where the coins don't match the nodes.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the coins in each node, and can the number of coins in a node be negative?
Can the tree be empty or contain null nodes, and if so, how should I handle those cases?
Does the tree have to be a complete or balanced binary tree, or can it be arbitrarily shaped?
Are we only concerned with the *minimum* number of moves required to distribute the coins?
If a node has excess coins, can those coins be directly transferred to its descendants (grandchildren, etc.) or only to its immediate children?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Look at each connection between two people (nodes) and consider every possible number of coins we could move across that connection.
For each choice of coin movements, check if that movement makes things better for everyone involved: does it bring each person closer to having exactly one coin?
Continue exploring different coin movements, going down the tree to each person (node) and trying out various amounts of coins to shift.
Keep track of how many coin movements it takes for each different way of moving coins around.
At the end, pick the way that took the fewest total coin movements. That is our best answer.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def distribute_coins_brute_force(root):
    min_moves = float('inf')

    def calculate_moves(node, moves):
        nonlocal min_moves

        if not node:
            return 0

        # Recursively process left and right subtrees.
        left_coins = calculate_moves(node.left, moves)
        right_coins = calculate_moves(node.right, moves)

        coins_needed = 1 - node.value

        total_coins_to_redistribute = left_coins + right_coins + node.value
        
        # If the current node is None, it contributes zero coins and zero moves
        if node is None:
            return 0

        # Explore all possible coin distributions.
        if node.left:
            moves += abs(left_coins)

        if node.right:
            moves += abs(right_coins)

        if not node.left and not node.right:
            return node.value - 1

        coins_at_node = node.value + left_coins + right_coins
        coins_to_pass_up = coins_at_node - 1

        # If all nodes have been visited, update the minimum moves.
        if not root.left and not root.right:
            min_moves = min(min_moves, moves)

        return coins_to_pass_up

    total_moves = 0
    calculate_moves(root, total_moves)

    return int(min_moves)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each part of the tree (each node) either needs coins or has extra coins.
Start at the bottom of the tree (the leaves) and work your way up.
For each part, figure out if it needs coins from its parent or can give coins to its parent.
The number of coins sent up or requested is how far out of balance that part of the tree is.
Keep track of the number of coins that had to be moved (this is the number of moves).
The total number of moves needed to balance the whole tree is the answer.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def distribute_coins(root):
    number_of_moves = 0

    def dfs(node):
        nonlocal number_of_moves

        if not node:
            return 0

        # Recursively calculate the balance for the left and right subtrees.
        left_subtree_balance = dfs(node.left)
        right_subtree_balance = dfs(node.right)

        #The number of moves is incremented by the absolute value of the balance
        number_of_moves += abs(left_subtree_balance) + abs(right_subtree_balance)

        # Return the balance of the current node to its parent.
        # Balance is the excess coins at node and subtrees - 1 coin for node.
        return node.val + left_subtree_balance + right_subtree_balance - 1

    dfs(root)
    return number_of_moves

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 if the root is null as no moves are needed.
Single node tree	Return 0 because a single node tree will always be balanced.
Tree with all nodes having 1 coin	The algorithm correctly calculates 0 moves since the tree is already balanced.
Tree with coins concentrated on one side (highly skewed)	The recursive nature of the solution correctly propagates deficits/surpluses and calculates moves for each subtree.
Tree with maximum allowable nodes (large N)	Ensure the recursion depth doesn't exceed allowable limits, and that integer overflow doesn't occur in the coin counts.
Node values near Integer.MAX_VALUE or Integer.MIN_VALUE	Use long to avoid integer overflow when calculating the balance at each node and when adding the moves.
Unbalanced tree structure, deep on one side	Recursive algorithm handles unbalanced trees as it visits each node, calculating the coins moved in each subtree.
Tree where total coins does not equal the total nodes	The algorithm should still correctly compute the minimum moves required to distribute the existing coins; it does not need to handle cases where the coins don't match the nodes.