Leetcode discuss: 979. Distribute Coins in Binary Tree

Here is the link.

C# Need to work on a simple case study

July 18, 2020

979. Distribute Coins in Binary Tree

Introduction

It is my first algorithm in Leetcode mock interview. I spent over 30 minutes to think about so many ways to break through the problem. Nothing can lead me to a simple solution.

Ideas I thought about in mock interview
I know that root node has coins with val, and it should take away val - 1 coins. But I continued to think which way to go, I tried to build a table.
      Root node
      /               \
Left subtree       Right subtree

I tried to think about from bottom up, leaf node has only one connection to parent node, up/ down two directions.

I also think about from root node, how to determine if left subtree has extra coins, or righ subtree has extra coins. It is impossible that both has extra coins.

Tree algorithms
It is totally different experience to solve tree algorithms after six month break. Recursive thinking is most challenge task.

Follow up
July 19, 2020 12:17 PM
Case study
A simple tree with root node (coins = 3) left child (coins 0) left.left child (coins 0)
The root node need to move away 2, left child need move one coin to add, left.left need move one coin to add, in total, there are 2.

Follow up 7/19/2020 1:32 PM
Case study
I need to work on a test case and see if I can figure out the coins move correctly or not.

The idea to calculate total coins moved is to calculate each edge what is number of coins to move from node to it's parent node. It is easy to apply a post order traversal. -1 means parent node sends a coin to it's child, +1 means that the node sends a coin to it's parent node.

The total coins moved is to add sum of each edge's absolute value.

In summary, using post order traversal, and also determine how many coins to move to parent node each time. Starting from leaf node, a node will consider it's children nodes and then add itself to the parent node.

The coins moved in the above diagram is 3.

Recursive function design
Apply post order traversal, recursive function will return number of coins to move in direction.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _979_distribute_coins_in_binary_tree
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var node0  = new TreeNode(0);
            var node0B = new TreeNode(0);
            var node0C = new TreeNode(0);
            var node4  = new TreeNode(4);
            var node0D = new TreeNode(0);
            var node3  = new TreeNode(3);
            var node0E = new TreeNode(0);

            node0.left   = node0B;
            node0.right  = node0C;

            node0B.left  = node4;
            node0B.right = node0D;

            node0C.left  = node3;
            node0C.right = node0E;

            DistributeCoins(node0);

            Console.WriteLine(coinsMoved);
        }

        public static int coinsMoved; 
        public static int DistributeCoins(TreeNode root)
        {
            if (root == null)
                return 0;

            coinsMoved = 0;

            postOrderTraversal(root);

            return coinsMoved;
        }

        /// <summary>
        /// https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221939/C%2B%2B-with-picture-post-order-traversal
        /// go over the example in the above discuss 
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int postOrderTraversal(TreeNode root)
        {
            if (root == null)
                return 0;

            var left  = postOrderTraversal(root.left);
            var right = postOrderTraversal(root.right);

            coinsMoved += Math.Abs(left) + Math.Abs(right);

            return left + right + root.val - 1;
        }
    }
}