Design Gurus Logo
Distribute Coins in Binary Tree (medium)

Problem Statement

You are given a root node of the binary tree, having n nodes, where each node contains the node.val number of coins. There are total n coins in the whole tree.

In one move, you can choose any two adjacent nodes and move a coin from one node to another. You can either move coins from parent to child or child to parent.

Return the minimum number of moves required to ensure every node has exactly one coin.

Examples

Example 1:

  • Input: [1,0,2]
Image
  • Expected Output: 2
  • Justification: We can move one coin from the right child to the root, and then from the root to the left child. This requires 2 moves to balance the coins.

Example 2:

  • Input: [2,0,2,2,0,0]
Image
  • Expected Output: 4
  • Justification: Move one coin from the root node to its left node, which requires 1 move. After that, move one coin from root->left->left to root->left->right node, which requires 2 moves. Next, move one coin from root->right to root->right->left, which requires 1 move. Minimum number of moves required is 4.

Example 3:

  • Input: [4,0,0,0]
Image
  • Expected Output: 4
  • Justification: Move two coins from the root to its left child, and then move one coin from this left child to its left child. This requires 3 moves. Move 1 coin to the right child, and this requires 1 move. So, total 4 moves are required.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory