Leetcode 236 - Lowest Common Ancestor - preorder traversal search

LowestCommonAncestor_PreOrder.cs

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

namespace LowestCommonAncestor_Practice
{
     public class TreeNode
    {
        public TreeNode left;
        public TreeNode right;
        public int key;

        public TreeNode(int v)
        {
            key = v;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            TreeNode node1 = new TreeNode(9);
            node1.left = new TreeNode(5);
            node1.right = new TreeNode(8);
            node1.left.left = new TreeNode(1);
            node1.left.right = new TreeNode(4);
            node1.left.right.left = new TreeNode(2);
            node1.left.right.right = new TreeNode(3);

            node1.right.right = new TreeNode(8);
            node1.right.right.left = new TreeNode(6);

            TreeNode node = findLCA(node1, node1.left, node1.left.right.left);
            TreeNode nd2 = findLCA(node1, node1.left.right.right, node1.right.right);
            TreeNode nd3 = findLCA(node1, node1.left.left, node1.left.right.right); 
        }

        /* 
         * Very good workout 
         * 1. backtracking is used - good idea to use backtracking
         * 2. use List.RemoveAt api
         * 
         * 
         * 
         * Finds the path from root node to given root of the tree, Stores the
         * path in a List<int> path, returns true if path exists otherwise false
         * 
         */
        public static bool findPath(TreeNode root, List<TreeNode> path, TreeNode searchNode)
        {
            // base case
            if (root == null) 
                return false;
 
            // Store this node in path. The node will be removed if
            // not in path from root to k
            path.Add(root);
 
            // See if the k is same as root's key
            if (root == searchNode)
                return true;
 
            // Check if k is found in left or right sub-tree
            if ( (root.left  != null && findPath(root.left, path, searchNode)) ||
                 (root.right != null && findPath(root.right, path, searchNode)) )
                return true;
 
            // If not present in subtree rooted with root, remove root from
            // path[] and return false
            path.RemoveAt(path.Count -1);
            return false;
        }
 
        // Returns LCA if node n1, n2 are present in the given binary tree,
        // otherwise return -1
        public static TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q)
        {
            // to store paths to n1 and n2 from the root
            List<TreeNode>  path1 = new List<TreeNode>();
            List<TreeNode>  path2 = new List<TreeNode>();
 
            // Find paths from root to n1 and root to n2. If either n1 or n2
            // is not present, return -1
            if ( !findPath(root, path1, p) || !findPath(root, path2, q))
                  return null;
 
            /* Compare the paths to get the first different value */
            int i;
            for (i = 0; i < path1.Count && i < path2.Count ; i++)
                if (path1[i] != path2[i])
                    break;
            return path1[i-1];
        }
 
    }
}