CODEWITHSUNDEEP
javatree
user2998228
user2998228

Reputation: 241

Finding longest path of a tree structure

I have a tree structure that looks like the following:

Tree {
   Node root;
}

Node {
   List children;
}

And I'm trying to make a method that returns the length of the longest path. I've seen some solutions that work when it's a binary tree, but there is no limit to how many children nodes each node can have and that is where I'm running into problems.

Upvotes: 3

Views: 3850

Answers (2)

Alessio
Alessio

Reputation: 2068

I should do somethinkg like this

int getLongestPathLength(Node node) {
    if(node == null) return 0;
    int max = 0;
    for(Node child : node.children){
        max = Math.max(getLongestPathLength(child),max);
    }
    return 1+max;
}

Upvotes: 8

JRe
JRe

Reputation: 31

It seems what you are looking for it called the height of the root. You can see the basic algorithm to compute it here (similar to the one given in the previous answer): http://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-08.html.

Upvotes: 0

Related Questions