Lowest common ancestor: Using space complexity O(1) | Two linked list meet at LCA

 Feb. 23, 2022

Lowest common ancestor - Find LCA using space complexity O(1)

	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;
	}
	}
	}

view raw LowestCommonAncestorWithParent.cs hosted with ❤ by GitHub