Solution to Leetcode problem 979 Distribute Coins in Binary Tree

In this problem, we are asked the number of moves so that each node contains exactly one coin in a valued binary tree.

Problem statement

I really enjoyed this exercise. It is a fun exercise that is resolved by code that is quite simple and is quite satisfying. I am also setting a series a post on trees and algorithms (first post here), where I will explore more on the particularities of tree algorithms.

I was looking for an elegant recursive solution. That could be easily explained.

First, I needed to compute the weight of each subtree T, the weight of a subtree being defined by:

w(T) = numberOfCoins(T) - numberOfNodes(T)

This will help us with knowing if subtrees have too many, not enough, or just the right amount of coins. I also needed to define and compute the cost of each subtree T:

c(T) = { 
  - if w(T) = 0: the number of moves to distribute the coins in the
tree.
  - if w(T) > 0: the number of moves to distribute the coins in the tree and the number of moves to transfer the exceeding coins to the parent of T.
  - if w(T) < 0: the number of moves to get all the missing coins from the parent, and the number of moves to distribute coins in the tree.
}