Lowest Common Ancestor of two nodes in a binary tree

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

namespace ConsoleApplication1
{
    public class Node
    {
        private Node left;
        private Node right;
        private int value;
        public Node(Node left, Node right, int value)
        {
            this.left = left;
            this.right = right;
            this.value = value;
        }
        public Node getLeft()
        {
            return left;
        }
        public Node getRight()
        {
            return right;
        }
        public int getValue()
        {
            return value;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //Initializing the tree structure
            /*
                    8
                  /  \
                 5    9
                /  \    \
               4    6    11
                        /  \
                       10   12
            */
            Node ten = new Node(null, null, 10);
            Node twelve = new Node(null, null, 12);
            Node eleven = new Node(ten, twelve, 11);
            Node four = new Node(null, null, 4);
            Node six = new Node(null, null, 6);
            Node five = new Node(four, six, 5);
            Node nine = new Node(null, eleven, 9);
            Node root = new Node(five, nine, 8);
            Node n1 = ten;
            Node n2 = eleven;
            Hashtable ht = ConvertTreeToHashTable(root);
            int flag = 0;
            if (n1 != null && n2 != null && n1 != n2 && n1 != root && n2 != root)
            {
                ArrayList nodeList1 = new ArrayList();
                ArrayList nodeList2 = new ArrayList();
                nodeList1.Add(n1);
                nodeList2.Add(n2);
                while ((!nodeList1.Contains(root) || !nodeList2.Contains(root)) && flag == 0)
                {
                    if (!nodeList1.Contains(root))
                    {
                        ArrayList tempList = (ArrayList)ht[(Node)nodeList1[nodeList1.Count - 1]];
                        if (nodeList1[0] == n1)
                            nodeList1.RemoveAt(0);
                        //Get node with minimum distance from root
                        int index = -1, distance = -1;
                        for (int i = 0; i < tempList.Count; i++)
                        {
                            int tempDistance = GetDistance(ht, root, (Node)tempList[i]);
                            if (distance == -1)
                            {
                                distance = tempDistance;
                                index = i;
                            }
                            else
                            {
                                if (tempDistance < distance)
                                {
                                    distance = tempDistance;
                                    index = i;
                                }
                            }
                        }
                        nodeList1.Add(tempList[index]);
                    }

                    if (!nodeList2.Contains(root))
                    {
                        ArrayList tempList = (ArrayList)ht[(Node)nodeList2[nodeList2.Count - 1]];
                        if (nodeList2[0] == n2)
                            nodeList2.RemoveAt(0);
                        //Get node with minimum distance from root
                        int index = -1, distance = -1;
                        for (int i = 0; i < tempList.Count; i++)
                        {
                            int tempDistance = GetDistance(ht, root, (Node)tempList[i]);
                            if (distance == -1)
                            {
                                distance = tempDistance;
                                index = i;
                            }
                            else
                            {
                                if (tempDistance < distance)
                                {
                                    distance = tempDistance;
                                    index = i;
                                }
                            }
                        }
                        nodeList2.Add(tempList[index]);
                    }
                    //Check for common nodes between nodeList1 and nodeList2
                    for (int i = 0; i < nodeList1.Count; i++)
                    {
                        for (int j = 0; j < nodeList2.Count; j++)
                        {
                            if (nodeList1[i] == nodeList2[j])
                            {
                                Console.WriteLine("Lowest Common Ancestor of " + n1.getValue() + " and " + n2.getValue() + " is: " + ((Node)nodeList1[i]).getValue());
                                flag = 1;
                                break;
                            }
                        }
                        if (flag == 1)
                            break;
                    }
                }
            }
            if (flag == 0)
            {
                Console.WriteLine("There is no common ancestor of " + n1.getValue() + " and " + n2.getValue());
            }
        }

        public static Hashtable ConvertTreeToHashTable(Node root)
        {
            Hashtable ht = new Hashtable();
            if (root != null)
            {
                Queue q = new Queue();
                q.Enqueue(root);
                while (q.Count != 0)
                {
                    Node temp = (Node)q.Dequeue();
                    ht.Add(temp, null);
                    ArrayList nodeList = new ArrayList();
                    if (temp.getLeft() != null)
                    {
                        nodeList.Add(temp.getLeft());
                        ht[temp] = nodeList;
                        q.Enqueue(temp.getLeft());
                    }

                    if (temp.getRight() != null)
                    {
                        nodeList.Add(temp.getRight());
                        ht[temp] = nodeList;
                        q.Enqueue(temp.getRight());
                    }
                }
                Array keyArray = Array.CreateInstance(typeof(Node), ht.Count);
                ht.Keys.CopyTo(keyArray, 0);
                for (int i = 0; i < ht.Count; i++)
                {
                    ArrayList nodeList = (ArrayList)ht[keyArray.GetValue(i)];
                    for (int j = 0; nodeList != null && j < nodeList.Count; j++)
                    {
                        ArrayList tempList = (ArrayList)ht[nodeList[j]];
                        if (tempList != null)
                        {
                            if (!tempList.Contains((Node)keyArray.GetValue(i)))
                            {
                                tempList.Add((Node)keyArray.GetValue(i));
                                ht[nodeList[j]] = tempList;
                            }
                        }
                        else
                        {
                            tempList = new ArrayList();
                            tempList.Add((Node)keyArray.GetValue(i));
                            ht[nodeList[j]] = tempList;
                        }
                    }
                }
                return ht;
            }
            return null;
        }

        public static int GetDistance(Hashtable ht, Node sourceNode, Node destinationNode)
        {
            int distance = 0;
            if (ht != null && sourceNode != null && destinationNode!= null)
            {
                Stack<Node> sourceNodeStack = new Stack<Node>();
                Stack<Node> destinationNodeStack = new Stack<Node>();
                ArrayList nodeArrayList = new ArrayList();
                sourceNodeStack.Push(sourceNode);
                bool found = false;
                while (sourceNodeStack != null && sourceNodeStack.Count != 0 && found == false)
                {
                    int flag = 0;
                    while (sourceNodeStack.Count != 0 && found == false)
                    {
                        Node currentKey = sourceNodeStack.Pop();
                        nodeArrayList.Add(currentKey);
                        ArrayList nodeList = (ArrayList)ht[currentKey];
                        if (currentKey == destinationNode)
                        {
                            found = true;
                            break;
                        }
                        else
                        {
                            for (int col = 0; col < nodeList.Count; col++)
                            {
                                if (!nodeArrayList.Contains((Node)nodeList[col]))
                                {
                                    flag = 1;
                                    if ((Node)nodeList[col] == destinationNode)
                                    {
                                        found = true;
                                        break;
                                    }
                                    destinationNodeStack.Push((Node)nodeList[col]);
                                }
                            }
                        }
                    }
                    if (flag == 1)
                        distance++;

                    while (destinationNodeStack.Count != 0 && found == false)
                    {
                        sourceNodeStack.Push(destinationNodeStack.Pop());
                    }
                }
                if (found == true)
                {
                    return distance;
                }
            }
            return -1;
        }
    }
}

Output
======
Lowest Common Ancestor of 10 and 11 is: 9
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s