Published 2024-07-25

979. Distribute Coins in Binary Tree

leetcode

Problem:

LeetCode Problem 979: Distribute Coins in Binary Tree

You are given the root of a binary tree with "N" nodes, where each node in the tree has `Node.val` coins, and there are exactly `N` coins total. In one move, we may choose two adjacent nodes and transfer one coin from one node to another. (The move may be from parent to child, or child to parent.)

The goal is to return the minimum number of moves required to make every node have exactly one coin.

Solution Description:

To implement the solution, we need to use a Depth-First Search (DFS) algorithm to traverse the tree. At each node, we'll calculate the surplus or deficit of coins and propagate this value to its parent. This can be done recursively where each call returns the balance of coins for the subtree rooted at that node. The number of moves is accumulated based on the absolute balance values at each node.

Step-by-step approach:

  1. Traverse each node starting from the leaves using DFS.
  2. Calculate the balance of coins as the number of coins at the node minus one (since each node needs one coin to be balanced).
  3. Propagate the balance to the parent node to keep track of the total movements needed.
  4. Accumulate the total moves needed based on the absolute values of the balances.

Time Complexity: O(N), where N is the number of nodes in the tree because we visit each node exactly once. Space Complexity: O(H), where H is the height of the tree due to the recursion stack.

Example:

Consider a tree where the root node has 3 coins, the left child has 0 coins, and the right child has 0 coins: 

  3
 / \
0   0

To balance this:

  • Move 1 coin from the root to the left child
  • Move 1 coin from the root to the right child

This requires 2 moves.

Setup:

We will define a recursive helper function `dfs` within the main function. The main function will initiate the DFS call and return the total number of moves.

Test Execution:

We will design comprehensive test cases to verify the solution, ensuring that each part of the tree is correctly balanced and the output matches the expected results.

Plan:

  1. Initialize a variable to keep track of the total moves.
  2. Implement the `dfs` function to process each node.
  3. Traverse the tree using `dfs` starting from the root node.
  4. Return the total moves after the DFS completes.
// Helper definitions:
const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

/**
 * Definition for a binary tree node.
 * @param {number} value
 * @param {TreeNode} left
 * @param {TreeNode} right
 */
function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

/**
 * Main function to distribute coins in a binary tree
 * @param {TreeNode} root
 * @returns {number}
 */
function distributeCoins(root) {
  let totalMoves = 0;

  return totalMoves;
}

// Test cases
const testCases = [
  { root: new TreeNode(3, new TreeNode(0), new TreeNode(0)), expected: 2 },
  { root: new TreeNode(0, new TreeNode(3), null), expected: 3 },
  { root: new TreeNode(1, new TreeNode(0), new TreeNode(2)), expected: 2 },
  { root: new TreeNode(1, new TreeNode(0, new TreeNode(3)), new TreeNode(0)), expected: 4 },
  { root: new TreeNode(1), expected: 0 } // Single node, no moves needed
];

testCases.forEach((test, index) => {
  const result = distributeCoins(test.root);
  console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});
© d)zharii. sitemap