Diameter of 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
            Node bottomFirst = new Node(null, null, 1);
            Node bottomSecond = new Node(null, null, 4);
            Node bottomThird = new Node(null, null, 7);
            Node bottomFourth = new Node(null, null, 12);
            Node middleFirst = new Node(bottomFirst, bottomSecond, 3);
            Node middleSecond = new Node(bottomThird, bottomFourth, 10);
            Node root = new Node(middleFirst, middleSecond, 5);
            Console.WriteLine("Diameter of the tree = " + GetDiameter(root));
        }

        public static int GetDiameter(Node root)
        {
            int diameter = 0;
            if (root != null)
            {
                Queue q = new Queue();
                q.Enqueue(root);
                ArrayList nodeList = new ArrayList();
                while (q.Count != 0)
                {
                    Node temp = (Node)q.Dequeue();
                    nodeList.Add(temp);
                    if (temp.getLeft() != null)
                    {
                        q.Enqueue(temp.getLeft());
                    }

                    if (temp.getRight() != null)
                    {
                        q.Enqueue(temp.getRight());
                    }
                }
                for (int i = 0; i < nodeList.Count - 1; i++)
                {
                    for (int j = i + 1; j < nodeList.Count; j++)
                    {
                        if (i == 0 && j == 1)
                        {
                            diameter = GetDistance(root, (Node)nodeList[i], (Node)nodeList[j]);
                        }
                        else
                        {
                            int tempDiameter = GetDistance(root, (Node)nodeList[i], (Node)nodeList[j]);
                            if (tempDiameter > diameter)
                            {
                                diameter = tempDiameter;
                            }
                        }
                    }
                }
            }
            return diameter;
        }

        public static int GetDistance(Node root, Node sourceNode, Node destinationNode)
        {
            int distance = 0;
            Hashtable ht = new Hashtable();
            if (root != null && sourceNode != null && destinationNode!= 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;
                        }
                    }
                }
                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
======
Diameter of the tree = 4
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