Printing nodes at a specified distance from a given node in a generic 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);
            Node sourceNode = bottomThird;
            int distance = 2;
            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());
                    }
                }
                Console.WriteLine("Before Transformation");
                Console.WriteLine("=====================");
                foreach (Node key in ht.Keys)
                {
                    Console.Write(key.getValue() + " --> ");
                    ArrayList nodeList = (ArrayList)ht[key];
                    for (int i = 0; nodeList != null && i < nodeList.Count; i++)
                    {
                        Console.Write(((Node)nodeList[i]).getValue() + " ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine("=====================");
                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;
                        }
                    }
                }
                Console.WriteLine("After Transformation");
                Console.WriteLine("=====================");
                foreach (Node key in ht.Keys)
                {
                    Console.Write(key.getValue() + " --> ");
                    ArrayList nodeList = (ArrayList)ht[key];
                    for (int i = 0; nodeList != null && i < nodeList.Count; i++)
                    {
                        Console.Write(((Node)nodeList[i]).getValue() + " ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine("=====================");
                Stack<Node> sourceNodeStack = new Stack<Node>();
                Stack<Node> destinationNodeStack = new Stack<Node>();
                ArrayList nodeArrayList = new ArrayList();
                sourceNodeStack.Push(sourceNode);
                int level = 0;
                while (level < distance)
                {
                    int flag = 0;
                    if (sourceNodeStack != null && sourceNodeStack.Count != 0)
                    {
                        while (sourceNodeStack.Count != 0)
                        {
                            Node currentKey = sourceNodeStack.Pop();
                            nodeArrayList.Add(currentKey);
                            ArrayList nodeList = (ArrayList)ht[currentKey];
                            for (int col = 0; col < nodeList.Count; col++)
                            {
                                if (!nodeArrayList.Contains((Node)nodeList[col]))
                                {
                                    destinationNodeStack.Push((Node)nodeList[col]);
                                    flag = 1;
                                }
                            }
                        }
                        //Copying destinationNodeStack to sourceNodeStack
                        while (destinationNodeStack.Count != 0)
                        {
                            sourceNodeStack.Push(destinationNodeStack.Pop());
                        }
                        if (flag == 1)
                            level++;
                    }
                    else
                    {
                        Console.WriteLine("No nodes found !!!");
                        level = -1;
                        break;
                    }
                }
                if (level != -1)
                {
                    Console.WriteLine("Nodes at distance " + distance.ToString() + " from node " + sourceNode.getValue() + ":");
                    while (sourceNodeStack.Count != 0)
                    {
                        Console.Write(((Node)sourceNodeStack.Pop()).getValue() + " ");
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}

Output
======
Before Transformation
=====================
5 --> 3 10
1 -->
10 --> 7 12
12 -->
3 --> 1 4
4 -->
7 -->
=====================
After Transformation
=====================
5 --> 3 10
1 --> 3
10 --> 7 12 5
12 --> 10
3 --> 1 4 5
4 --> 3
7 --> 10
=====================
Nodes at distance 2 from node 7:
12 5
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