Leetcode discuss: 1530. Number of Good Leaf Nodes Pairs

 Here is my discuss post. 

C# Find root to leaf node path using 0 and 1 two digit string

August 21, 2020
1530. Number of Good Leaf Nodes Pairs

Introduction
It is time for me to work on aother 40 algorithm to prepare FANG company phone screen on Sept. 5, 2020. I started to work on tree algorithms. To train myself properly, I have to write down what I do correctly this practice, what goes wrong this practice as well.

Find root to leaf node path using 0 and 1 two digit string
It is easy to come out the idea to map the path from root to leaf node since there are two direcitons each step, either going left or right. Using 0 to stand for left, 1 to stand for right. First digit 0 to represent start from root node, no meaning.

Case study
Simple tree with only one node, so there are no pair, return 0.
A tree with three nodes, root with value 1, left with value 2, right with value 3.
So root to left node's path is 00, first 0 stands for starting from root node, second 0 means go to left from root node.
Two paths using two strings "00" and "01"' can determine the distance two leaf node. Count edge not counting vertex.

Here are highlights of my practice:

1. Choose preorder traversal, practice backtracking using one C# List<> variable;
2. Test and make sure that 0 or 1 is saved into the path, not root.val;
3. Backtracking is tested, remove early return after leaf node is found; in other words, backtracking is needed after leaf node is found;
4. It is challenge to calculate path using two strings representing directions from root to leaf node.
5. More on step 4, reason about calculation: var pathSum = first.Count + second.Count - 2; // count edges, not vertexs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    /// <summary>
        /// The idea is to represent each leaf node using a string to represent the path from root to the leaf node
        /// 0 - left, 1 - right
        /// start from root node, 001, first 0 means nothing, then left, right, 
        /// so 001 and 011 two leaf nodes's distance should be length("01") + length("11") = 4. 
        /// Edge is counted and the first different digit from leftmost will start to count. 
        /// </summary>
        /// <param name="root"></param>
        /// <param name="distance"></param>
        /// <returns></returns>
        /// unit test case:
        /// Case 1: Tree with one node, value 1 - distance 1, return 0 
        /// Case 2: Tree with three nodes, value 1, left value 2, right value 3, - distance 1, return 1
        public int CountPairs(TreeNode root, int distance)
        {
            if (root == null || distance <= 0) 
                return 0; 

            // traverse the tree using preorder traversal, and then record all leaf node's string to 
            // represent the path from root node to leaf node. 
            // Go over the list of leaf nodes with path information, compare any two of them and see how many
            // to fit in the given distance
            var path = new List<int>();
            var paths = new List<IList<int>>(); 

            runPreorderTraversal(root, path, paths, true);

            var length = paths.Count; // 2
            var count = 0; 
            for (int i = 0; i < length; i++)
            {
                for (int j = i + 1; j < length; j++)
                {
                    var first = paths[i];
                    var second = paths[j];
                    var pathSum = first.Count + second.Count - 2;  // count edges, not vertexs
                    var sharedEdges = 0; 
                    for (int index = 1; index < Math.Min(first.Count, second.Count); index++)
                    {
                        if (first[index] == second[index])
                        {
                            sharedEdges++;
                            continue;
                        }
                        else
                        {
                            break;
                        }
                    }

                    var current = pathSum - sharedEdges * 2;
                    if (current <= distance)
                    {
                        count++;
                    }
                }
            }

            return count; 
        }

        private void runPreorderTraversal(TreeNode root, List<int> path, List<IList<int>> paths, bool isLeft)
        {
            if (root == null)
            {
                return;
            }

            var rootValue = root.val; // 1
            path.Add(isLeft? 0 : 1); // [1, 2]

            if (root.left == null && root.right == null)
            {
                var copy = new List<int>(path);
                paths.Add(copy); // {[1, 2]}
                // return;   - concern of backtracking - remove early return
            }

            runPreorderTraversal(root.left, path, paths, true);
            runPreorderTraversal(root.right, path, paths, false); // 3

            // backtracking
            path.RemoveAt(path.Count - 1); 
        }
}

backtrackingroot to leaf pathpath comparison