Problem Statement:
NOTE : THIS APPROACH IS FOR BINARY TREE ( NOT FOR BST)
Approach:
Lowest Common ancestor is the node to which the two nodes lie on the different sides,one node to its right and other node to its left.
If both the nodes are to its left than LCA is on left side of the node and if both the nodes are to its right than LCA is on right side of the node.
This can be implemented recursively using the bottom up approach with O(n) Complexity..
ASSUMPTION : Two nodes exist in the tree. Not Checking for there presence in this solution...
ASSUMPTION : Two nodes exist in the tree. Not Checking for there presence in this solution...
Here is the working C# Code. Just Copy and paste...
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LowestCommonAncestor
{
// Tree Node Definition
public class Tree
{
public int item;
public Tree left;
public Tree right;
public Tree(int val)
{
item = val;
left = null;
right = null;
}
}
class Program
{
static void Main(string[] args)
{
/* Constructed binary tree is
10
/ \
7 30
/ \ /
4 8 16
/
2
*/
Tree root = new Tree(10);
root.left = new Tree(7);
root.right = new Tree(30);
root.left.left = new Tree(4);
root.left.right = new Tree(8);
root.right.left = new Tree(16);
root.left.left.left = new Tree(2);
Tree p = root.left.left.left;
Tree q = root.left.right;
Tree LCA = findLowestCommonAncestor(root, p, q);
Console.WriteLine(LCA.item);
}
// Function To find the Lowest Common Ancestor
public static Tree findLowestCommonAncestor(Tree root, Tree p, Tree q)
{
if (root == null)
return null;
if (root == p || root == q)
return root;
Tree left = findLowestCommonAncestor(root.left, p, q);
Tree right = findLowestCommonAncestor(root.right, p, q);
if (left != null && right != null)
return root;
if (left != null)
return left;
else
return right;
}
}
}
Complexity :
Time Complexity : O(n), Since this is bottom up approach and each node is touched only once...
Hope you liked it.. For any suggestion or question please comment below...
I am having a hard time understanding the recursion. Can you please do a dry run of this on a small tree ? Thanks again.
ReplyDeleteHere is a video on lowest common ancestor problem with step by step explanation:
ReplyDeletehttps://www.youtube.com/watch?v=NBcqBddFbZw