1650. Lowest Common Ancestor of a Binary Tree III

 March 8, 2022

Here is the link. 

C# | Space complexity O(1)

March 6, 2022
Introduction
I chose to practice mock interview on interviewing dot io, and then the interviewer asked me to work on this algorithm; and also asked me to come out the algorithm using O(1) space instead of O(h) space.

A simple trick | p -> p's parent -> ... -> root -> q -> q's parent -> ...-> LCA
It is kind of tricky to prove that a two linked list will end up a LCA node, lowest common ancestor. I think that the difference between p and q in terms of level in the tree is fixed, so it is a working idea to travel from p to it's parent node until the root node and then switch to q node and travel to LCA.

Node p to root node - denoted as pToRoot
Node q to root node - denoted as qToRoot
LCA to root node - denoted as LCAToRoot
So the distance p to root -> q ->...->LCA should be pToRoot + qToRoot - LCAToRoot
Likewise, q to root -> p ->...->LCA should also be pToRoot + qToRoot - LCAToRoot.
And also LCAToRoot <= Math.Min(pToRoot, qToRoot), so (pToRoot + qToRoot - LCAToRoot) >= 0.

Two linked lists:
p -> p's parent -> ... -> root -> q -> q's parent -> ...-> LCA
same applies to node q

The following C# code passes online judge

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

namespace Cons1650_lowest_common_ancestor
{
    class Program
    {
        public class Node
        {
            public int val;
            public Node left;
            public Node right;
            public Node parent;

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

        static void Main(string[] args)
        {
            var node3 = new Node(3);
            node3.left = new Node(5);
            node3.left.left = new Node(6);
            node3.left.right = new Node(2);
            node3.left.right.left = new Node(7);
            node3.left.right.right = new Node(4);
            node3.right = new Node(1);
            node3.right.left = new Node(0);
            node3.right.right = new Node(8);

            node3.left.parent = node3;
            node3.right.parent = node3;
            node3.left.left.parent = node3.left;
            node3.left.right.parent = node3.left;
            node3.left.right.left.parent = node3.left.right;
            node3.left.right.right.parent = node3.left.right;

            var test = new Program();
            var result = test.LowestCommonAncestor(node3.left, node3.right);
            Debug.Assert(result.val == 3);
        }

        public Node LowestCommonAncestor(Node p, Node q)
        {
            if (p == null || q == null)
                return null;

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

                if (start2.parent == null)
                    start2 = p;
                else 
                    start2 = start2.parent;
            }

            return start;
        }
    }
}