leetcode discuss: 236. Lowest Common Ancestor of a Binary Tree

Here is my post.

C# Tuple<TreeNode, int> design talk and quick practice in May 25 2020

It is the day one for me to go back to algorithm practice after a few months break since coronavirus. Facebook recruiter sent out invitation to apply again after Mark Zuckberg embraces remote work on May 22, 2020 in remote hiring decision. I went to onsite in August 2019 in MPK, California.

There is hope for hard working people who struggles to find opportunity to use talent and try hard to seek challenging positions. All need good research, hard working. There is always opportunity for hard working people no matter what is happening.

I just practice one more time using Tuple<TreeNode, int>. Here are highlights I like to talk about related to design and things learned through the practice.

1. Design a recurisive function to count how many nodes found in subtree, if Lowest Common Ancestor (LCA) found or not;
2. Apply postorder traversal so every node will be checked once;
3. Every node will be compared to p and q, increment count if it is true somehow explicitly or implicitly;
4. Determine current node is LCA or not;
5. C# strong type Tuple<TreeNode, int> is a better choice compared to a class or C# ArrayList.
6. Review my last practice written on May 1, 2020. Here is the link.
7. Pay attention to return null instead of Tuple<TreeNode, int>(null, 0). More work is needed.

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

namespace _236_lowest_common_ancestor_Tuple
{
    class Program
    {
        static void Main(string[] args)
        {
        }

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

        /// <summary>
        /// warmup practice on May 25, 2020
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            // apply post order, and also using strong type Tuple<TreeNode, int> as return argument, 
            // first one is LCA TreeNode, second one is the count of nodes found
            var tuple = traversePostOrder(root, p, q);
            return tuple.Item1;
        }

        /// <summary>
        /// apply postorder, bottom up
        /// check two results:
        /// LCA and count of nodes found
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        private Tuple<TreeNode, int> traversePostOrder(TreeNode root, TreeNode p, TreeNode q)
        {
            if (root == null)
            {
                return null;
            }

            // postorder
            var left = traversePostOrder(root.left, p, q);
            var right = traversePostOrder(root.right, p, q);

            if (left != null && left.Item1 != null)
            {
                return left;
            }

            if (right != null && right.Item1 != null)
            {
                return right;
            }

            var countRoot = (root == p || root == q) ? 1 : 0;
            var leftCount = 0;
            if (left != null)
            {
                leftCount += left.Item2;
            }

            var rightCount = 0;
            if (right != null)
            {
                rightCount += right.Item2;
            }

            var count = leftCount + rightCount + countRoot;
            if (count == 2)
            {
                return new Tuple<TreeNode, int>(root, 2);
            }

            return new Tuple<TreeNode, int>(null, count);
        }
    }
}