CODEWITHSUNDEEP
c#algorithmbinary-tree
Martin
Martin

Reputation: 40593

Find the depth of a node in C#

I have a list of unsorted objects. Those objects represent a binary tree.

List of objects: 

new List<Object> 
{
    new { Id = 3, Left = /, Right = / }
    new { Id = 5, Left = /, Right = / }
    new { Id = 4, Left = 2, Right = 5 }
    new { Id = 2, Left = 1, Right = 3 }
    new { Id = 1, Left = /, Right = / }
}

Binary Tree:

      4
    /  \
   2    5
  / \
 1  3

I need an algorithm which will find the depth of any of these nodes. The only algorithm I am aware of is Depth-first search. It implies that I have to convert the list of objects into a tree. Considering that .NET has no explicit tree data structure how would you approach this problem? Do I have to convert the data structure into a tree (I don't really want to write all the code). Is there other algo?

Upvotes: 2

Views: 4335

Answers (3)

Jeffrey L Whitledge
Jeffrey L Whitledge

Reputation: 59513

You could just make a Dictionary<int,int> parents. Store the node ID as the key, and the node's parent as the value. Note, that this means storing zero, one, or two records in the dictionary for each object in the original list. Then to find the depth of a node, just count the number of times you can get a parent node before you run out. Something like this:

public static int NodeDepth(int node, Dictionary<int,int> parents)
{
     int depth = 0;
     while (parents.ContainsKey(node))
     {
          node = parents[node];
          depth++;
     }
     return depth;
}

Upvotes: 0

tbischel
tbischel

Reputation: 6477

you could just add your objects to a dictionary, using each of the left and right values as keys and the Id as the value (basically a reverse map). then you write your recursive function like this...

Dictionary<int, int> map;
    int depth(int node)
    {
        if (!map.ContainsKey(node))
            return 0;
        return depth(map[node]) + 1;
    }

Upvotes: 1

Yuriy Faktorovich
Yuriy Faktorovich

Reputation: 68717

int nodeToFind = 2;
var currentNode = list.Single(n => n.Id == nodeToFind);
int depth = 0;
while ((currentNode = list
    .FirstOrDefault(i => i.Left == currentNode.Id || i.Right == currentNode.Id)) != null)

    depth++;
Console.WriteLine(depth);

Simple, but inefficient.

Upvotes: 5

Related Questions