Find the maximum depth of a tree

Question

I have a tree data structure with N first-level child nodes that have childs too.

For example:

• Root
• Node1
• Node11
• Node111
• Node1111
• Node12
• Node2
• Node21
• Node211

I would like to know which of the braches has the biggest depth. As in the previous example it will be

Node1 - Node11 - Node111 - Node1111

that has a depth of four levels.

Any suggestion?

Thanks!

Answer 1

The most straightforward is a brute force algorithm which enumerates every path, saves pointers to all the nodes, and measures the depth. For each path which is longer than a previous path, forget all other paths and only remember the longest.

Answer 2

The deepest branch from a node is:
    the longest of the respective deepest branches from each child node
    prepended with the current node.

Answer 3

Traverse the tree depth-first or breadth-first, assigning to each node its depth. Remember the node with the highest depth.

Navigate recusrivle back from that node to the root. This gives you the lngest branch. There might be more than one branch with the same length.

Answer 4

You must check all nodes. Several months ago I implemented this algorithm in this way:

class Node
{
    public String Name { get; private set; }
    public IList<Node> Childs { get; private set; }

    public Node(String name)
    {
        Name = name;
        Childs = new List<Node>();
    }

    public List<Node> Depth
    {
        get
        {
            List<Node> path = new List<Node>();
            foreach (Node node in Childs)
            {
                List<Node> tmp = node.Depth;
                if (tmp.Count > path.Count)
                    path = tmp;
            }
            path.Insert(0, this);
            return path;
        }
    }

    public override string ToString()
    {
        return Name;
    }
}

Example test:

Node node1111 = new Node("Node1111");
Node node111 = new Node("Node111");
Node node11 = new Node("Node11");
Node node12 = new Node("Node12");
Node node1 = new Node("Node1");
Node root = new Node("Root");
Node node2 = new Node("Node2");
Node node21 = new Node("Node21");
Node node211 = new Node("Node211");
root.Childs.Add(node1);
root.Childs.Add(node2);
node1.Childs.Add(node11);
node1.Childs.Add(node12);
node11.Childs.Add(node111);
node111.Childs.Add(node1111);
node2.Childs.Add(node21);
node21.Childs.Add(node211);

List<Node> path = root.Depth;
foreach (Node n in path)
    Console.Write(String.Format("{0} - ", n.ToString()));

Console.WriteLine();

Node node2111 = new Node("Node2111");
node2111.Childs.Add(new Node("Node21111"));
node211.Childs.Add(node2111);

path = root.Depth;
foreach (Node n in path)
    Console.Write(String.Format("{0} - ", n.ToString()));

Console.WriteLine();

Console output:

Root - Node1 - Node11 - Node111 - Node1111 -
Root - Node2 - Node21 - Node211 - Node2111 - Node21111 -

Answer 5

If you have any form of iterator over your tree then you can use a perfectly mundane approach to the max depth.

Here's silly one-liner showing the concept for finding maximum reachable filesystem depth using UNIX find, awk and tr:

find / -depth | tr -dc '/\n' \
    | awk '{if (length($0) > max) { max=length($0)}}; END {print max}'

... find is the iterator, tr is a data manipulation "translating" one set of characters into another (in this case it's being used to -d (delete) the complement (-c) of the single character set being specified (/). So it converts any UNIX full path into just the / separators. From there I just find the longest line of input ... and that's my result.

Of course this approach won't help you much with your homework assignment. But the concept should be clear. :)