Find lowest common ancestor in Binary Search Tree

Question

I've got the following code to find the lowest common ancestor (the lowest node that has both a and b as descendants):

public static Node LCA(Node root, Node a, Node b)
{
    if (root == null)
        return null;

    if (root.IData == a.IData || root.IData == b.IData)
        return root;

    if (root.RightChild != null && (root.RightChild.IData == a.IData || root.RightChild.IData == b.IData))
        return root;

    if (root.LeftChild != null && (root.LeftChild.IData == a.IData || root.LeftChild.IData == b.IData))
        return root;

    if (root.IData > a.IData && root.IData > b.IData)
        return LCA(root.LeftChild, a, b);
    else if (root.IData < a.IData && root.IData < b.IData)
        return LCA(root.RightChild, a, b);
    else
        return root;
}

The binary search tree is

                      20
                     /  \
                    8    22
                  /   \
                 4     12 
                      /  \
                    10    14

Question

It is failing for the following cases:

LCA (4, 8) = 20 but should be 8.

LCA (8, 12) = 20 but should be 8

LCA (8, 23) = 20, non-existent number (23) as parameter.

Any thoughts?

Where Node is

class Node
{
 public int IData {get; set;}
 public Node RightChild {get; set;}
 public Node LeftChild {get; set;}
}

Answer 1

If the IData of root is different from both, a's and b's, but one of root's children has the same IData as either of the two, you return root, but by your definition, you should return the child if both nodes are in the same subtree. Since you also want to check that both nodes actually are in the tree, that check must be performed before any return.

public static Node LCA(Node root, Node a, Node b)
{
    if (root == null) return null;
    // what if a == null or b == null ?
    Node small, large, current = root;
    if (a.IData < b.IData)
    {
        small = a;
        large = b;
    }
    else
    {
        small = b;
        large = a;
    }
    if (large.IData < current.IData)
    {
        do
        {
            current = current.LeftChild;
        }while(current != null && large.IData < current.IData);
        if (current == null) return null;
        if (current.IData < small.IData) return LCA(current,small,large);
        // if we get here, current has the same IData as one of the two, the two are
        // in different subtrees, or not both are in the tree
        if (contains(current,small) && contains(current,large)) return current;
        // at least one isn't in the tree, return null
        return null;
    }
    else if (current.IData < small.IData)
    {
        // the symmetric case, too lazy to type it out
    }
    else // Not both in the same subtree
    {
        if (contains(current,small) && contains(current,large)) return current;
    }
    return null; // at least one not in tree
}

public static bool contains(Node root, Node target)
{
    if (root == null) return false;
    if (root.IData == target.IData) return true;
    if (root.IData < target.IData) return contains(root.RightChild,target);
    return contains(root.LeftChild,target);
}

Answer 2

Does IData have the equality operator (==) defined? If not, you are just comparing the references and not the object themselves.

This explains it fairly well: http://www.ikriv.com/en/prog/info/dotnet/ObjectEquality.html

Answer 3

Here is C# version:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LCA
{
    class Node
    {
        public Node(int data, Node a, Node b)
        {
            IData = data;
            LeftChild = a;
            RightChild = b;
        }

        public int IData { get; set; }
        public Node RightChild { get; set; }
        public Node LeftChild { get; set; }
    }

    class Program
    {
        static Node a = new Node(10, null, null);
        static Node b = new Node(14, null, null);
        static Node ab = new Node(12, a, b);
        static Node c = new Node(4, null, null);
        static Node ac = new Node(8, c, ab);
        static Node d = new Node(22, null, null);
        static Node root = new Node(20, ac, d);

        static void Main(string[] args)
        {
            string line;
            line = Console.ReadLine();
            string[] ip = line.Split(' ');
            int ip1 = -1;
            int ip2 = -1;

            if (ip.Length == 2)
            {
                Int32.TryParse(ip[0], out ip1);
                Int32.TryParse(ip[1], out ip2);
                int i = -1;
                Node node = null;
                Node node1 = new Node(ip1, null, null);
                Node node2 = new Node(ip2, null, null);
                if (contains(root, node1))
                {
                    if (!contains(root, node2))
                        node = node1;
                }
                else
                {
                    if (!contains(root, node2))
                        node = new Node(-1, null, null);
                    else
                        node = node2;
                }
                if (node == null)
                    node = LCA(root, node1, node2);

                Int32.TryParse(node.IData.ToString(), out i);

                Console.WriteLine(i);
                Console.ReadLine();
            }
        }

        public static Node LCA(Node root, Node a, Node b)
        {
            if (root == null) return null;

            Node small, large, current = root;
            if (a.IData < b.IData)
            {
                small = a;
                large = b;
            }
            else
            {
                small = b;
                large = a;
            }
            if (large.IData < current.IData)
            {
                do
                {
                    current = current.LeftChild;
                } while (current != null && large.IData < current.IData);
                if (current == null) return null;
                if (current.IData < small.IData) return LCA(current, small, large);
                // if we get here, current has the same IData as one of the two, the two are
                // in different subtrees, or not both are in the tree
                if (contains(current, small) && contains(current, large)) return current;
                // at least one isn't in the tree, return null
                return null;
            }
            else if (current.IData < small.IData)
            {
                do
                {
                    current = current.RightChild;
                } while (current != null && current.IData < small.IData);
                if (current == null) return null;
                if (current.IData < small.IData) return LCA(current, small, large);
                // if we get here, current has the same IData as one of the two, the two are
                // in different subtrees, or not both are in the tree
                if (contains(current, small) && contains(current, large)) return current;
                // at least one isn't in the tree, return null
                return null;
            }
            else // Not both in the same subtree
            {
                if (contains(current, small) && contains(current, large)) return current;
            }
            return null; // at least one not in tree
        }

        public static bool contains(Node root, Node target)
        {
            if (root == null) return false;
            if (root.IData == target.IData) return true;
            if (root.IData < target.IData) return contains(root.RightChild, target);
            return contains(root.LeftChild, target);
        }
    }
}

Answer 4

Here you go:

Console.WriteLine("\n\n /* Lowest Common Ancestor */");
int v1 = 4, v2 = 8;
Node lca = LCA(Root, v1, v2);
Console.WriteLine("LCA of {0} and {1} is: {2}", v1, v2, (lca != null ? lca.Data.ToString() : "No LCA Found"));


public static Node LCA(Node root, int v1, int v2)
{
        if (root == null)
            return null;

        if (root.Data > v1 && root.Data > v2)
            return LCA(root.Left, v1, v2);
        else if (root.Data < v1 && root.Data < v2)
            return LCA(root.Right, v1, v2);
        else
            return root;
}

Answer 5

Just adding c# iterative version for finding common ancestor in Binary Search tree for reference:

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
    {
        //ensure both elements are there in the bst
        var n1 = this.BstFind(e1, throwIfNotFound: true);
        if(e1 == e2)
        {
            return n1;
        }
        this.BstFind(e2, throwIfNotFound: true);
        BinaryTreeNode leastCommonAcncestor = this._root;
        var iterativeNode = this._root;
        while(iterativeNode != null)
        {
            if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
            {
                iterativeNode = iterativeNode.Left;
            }
            else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
            {
                iterativeNode = iterativeNode.Right;
            }
            else
            {
                //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                return iterativeNode;
            }
        }

Where Find is defined as below

public BinaryTreeNode Find(int e, bool throwIfNotFound)
        {
            var iterativenode = this._root;
            while(iterativenode != null)
            {
                if(iterativenode.Element == e)
                {
                    return iterativenode;
                }
                if(e < iterativenode.Element)
                {
                    iterativenode = iterativenode.Left;
                }
                if(e > iterativenode.Element)
                {
                    iterativenode = iterativenode.Right;
                }
            }
            if(throwIfNotFound)
            {
                throw new Exception(string.Format("Given element {0} is not found", e);
            }
            return null;
        }

And BinaryTreeNode is defined as:

class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;

    }

**tests**

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
            }
        }

Answer 6

public static Node LCA(Node root, Node a, Node b)
{

    if (root == null)
        return null;

    if (root.IData > a.IData && root.IData > b.IData)
        return LCA(root.LeftChild, a, b);
    if (root.IData < a.IData && root.IData < b.IData)
        return LCA(root.RightChild, a, b);

    return root;
}