Lowest common ancestor - find LCA in a given binary tree, node p and node q. Use space O(1) to find LCA - interviewing.io mock interview, interviewer shared the following idea. Feb. 22, 2022

LowestCommonAncestorWithParent.cs

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

namespace LowestCommonAncestorWithParent
{
    class Program
    {
        static void Main(string[] args)
        {
            var node1 = new Node(1);
            node1.left = new Node(2);
            node1.left.left = new Node(3);
            node1.left.right = new Node(4);
            node1.left.right.right = new Node(5);

            node1.left.parent = node1;
            node1.left.left.parent = node1.left;
            node1.left.right.parent = node1.left;
            node1.left.right.right.parent = node1.left.right;

            var test = new Program();
            var LCA = test.LowestCommonAncestor(node1.left.left, node1.left.right.right);
            Debug.Assert(LCA.val == 2);
        }

        public class Node
        {
            public int val;
            public Node left;
            public Node right;
            public Node parent;

            public Node(int value)
            {
                val = value;
            }
        }

        /// <summary>
        /// node3->node2->node1->node5->node4->node2
        /// node5->node4->node2->node1->node3->node2
        /// By observing the above two linked list, two linked list meet at LCA - node2
        /// node3 will go up it's parent node, until the root node and continue to travel to node5
        /// node5 will go up it's parent node, untilt the root node and continue to travel to node3
        /// Space complexity is O(1)
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public Node LowestCommonAncestor(Node p, Node q)
        {
            if (p == null || q == null)
                return null;

            var copyP = p;
            var copyQ = q;
            while (copyP != copyQ)
            {
                if (copyP.parent == null)
                {
                    copyP = q;
                }
                else
                {
                    copyP = copyP.parent;
                }

                if (copyQ.parent == null)
                {
                    copyQ = p;
                }
                else
                {
                    copyQ = copyQ.parent;
                }
            }

            return copyP;           
        }
    }
}