You are not logged in. Please login at to post your questions!


KETYES - Editorial



Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah




Graph Theory, Graph Traversal


Given a tree and a node, find the distance from the root to the node.


Traverse the tree using BFS or DFS and store the distance of each node from the root in a linked list, till the required node is found.


You need to find the distance of the given node from the root node (root node which is always 0). For that you have to start traversing the tree from the root node. For traversing the tree you can either use BFS or DFS (read more here). Every time a new node, lets say A, is found from another node, lets call it B, you add 1 to the distance of B from root and call it the distance of A from root. You store that distance in a linked list. When you find the required node you break from the loop, and print the required distance.

Following is the code with explanation in comments

        Stack<int>st=new Stack<int>();//declare a stack
        List<int>done=new List<int>();//declare a linked list to store already visited nodes
        List<int>dist=new List<int>();//declare another linked list to store distance of current node from popped node
        st.Push(0);//pushing root node, the source node
        done.Add(0);//adding root node to linked list, cause its visited
        dist.Add(0);//adding distance of root node from root node
        while(st.Count>0)//till all nodes are visited this will run
            int now=st.Pop();//popping current node
            int curdist=dist[done.IndexOf(now)];//extracting distance of current node from root node
            for(int i=0;i<n;i++)//iterating through all nodes

                if(arr[now,i]==1)//if its neighbour of popped node then this will be true
                    if(!done.Contains(i))//if its not visited already
                        done.Add(i);//add node to linked list
                        dist.Add(curdist+1);//add extracted distance+1 to distance linked list
                        st.Push(i);//push the node to the stack
        Console.WriteLine(dist[done.IndexOf(find)]);//print the required distance


Author's solution can be found above. Tester's solution can be found above.

asked 29 Mar '16, 19:34

chandubaba's gravatar image

3★chandubaba ♢
accept rate: 0%

edited 20 May '16, 11:41

admin's gravatar image

0★admin ♦♦

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 29 Mar '16, 19:34

question was seen: 659 times

last updated: 20 May '16, 11:41