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

Here is the link.

C# Find path from root to p practice on May 26, 2020

May 26, 2020

It is most important technique to learn how to achieve space optimization using backtracking. I like to write something for my practice on this preorder traversal and then find lowest common ancestor solution.

Here are highlights:

1. Only search one node in the function; Do one thing only principle.
2. Design recursive function with bool return.
3. Apply backtracking to achieve space optimization.
4. Get familiar how to write clean code;
5. Play with a simple tree: Root node value 1, left child is 2, right child is 3, p is node 3, root to p should be [1, 3]. Preorder traversal should be 1, 2, 3, so 2 is added to the path, and then 2 should be removed from the path, how to design using backtracking to remove 2?
6. Consider alternative design of recursive function, instead of return bool value, what else will be good as well?

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

namespace lowest_common_ancestor_236_codeReview
{
    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)
        {
        }        

        /// <summary>
        /// Leetcode 236 lowest common ancestor in binary tree
        /// Solution:
        /// 1. Apply preorder to search p and q in two traversal of tree;
        /// 2. Find path from root to p and path from root to q;
        /// 3. Find lowest common ancestor from those two paths. 
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            if (root == null || p == null || q == null)
            {
                return null;
            }

            var rootToP = new List<TreeNode>();
            var rootToQ = new List<TreeNode>();

            preorderTraverse(root, p, rootToP);
            preorderTraverse(root, q, rootToQ);

            if (rootToP.Count == 0 || rootToQ.Count == 0)
            {
                return null;
            }

            int index = 0;
            TreeNode ancestor = null;
            while (index < rootToP.Count && index < rootToQ.Count)
            {
                if (rootToP[index] != rootToQ[index])
                {
                    break;
                }

                ancestor = rootToP[index];                
               
                // next iteration
                index++;
            }

            return ancestor;
        }
        
        /// <summary>
        /// code review practice on May 26, 2020
        /// Design concerns:
        /// 1. Only search one node in the function; Do one thing only principle.
        /// 2. Design recursive function with bool return. 
        /// 3. Apply backtracking to achieve space optimization.
        /// 4. Get familiar how to write clean code; 
        /// 5. Play with a simple tree: Root node value 1, left child is 2, right child is 3
        /// p is node 3, root to p should be [1, 3]
        /// preorder traversal should be 1, 2, 3, so 2 is added to the path, and then 2 is 
        /// removed from the path
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="path"></param>
        private static bool preorderTraverse(TreeNode root, TreeNode p, List<TreeNode> path)
        {
            if (root == null)
            {
                return false;
            }

            path.Add(root);

            if (root == p)
            {
                return true;
            }

            var left  = preorderTraverse(root.left, p, path);
            var right = preorderTraverse(root.right,p, path);

            if (left || right)
            {
                return true; 
            }

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

            return false; 
        }
    }
}