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

Here is my post.

C# Tuple<TreeNode, int> design talk and second practice on May 25 2020

It is my most favorite tree algorithm. Starting from May 1, 2020, I use the algorithm to interview people again on interviewing dot io as a mock interviewer. I learn one more elegant solution using recursive function.

Here are highlights of my practice:

1. Apply recursive function, post order, and design the return using two arguments, different data type; integrate them seamlessly using Tuple<TreeNode, int>;
2. Lowest Common Ancester (LCA) can be solved using so many ways, always go for the easy one, short one, elgant one for interviews.
3. Consider this solution as your ideal solution in your next interview.
4. Code can be simplified to avoid returning null all the time. Leave it as an exercise for readers.

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;

            left  = left  == null ? new Tuple<TreeNode, int>(null, 0) : left;
            right = right == null ? new Tuple<TreeNode, int>(null, 0) : right;

            var count = left.Item2 + right.Item2 + countRoot;

            if (count == 2)
            {
                return new Tuple<TreeNode, int>(root, 2);
            }

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