Find the Lowest common ancestor in a binary tree

Problem Statement:

Find the Lowest common ancestor in a binary tree. Given the two nodes of a binary tree find the lowest common ancestor in the binary tree?

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...

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...