how to get the maximum depth of an html tree ?

Question

say i have an html page parsed via Nokogiri.

how can i find the maximum depth of the tree ? do i iterate through each element and count how many ancestors it has ? is there a more efficient approach ?

Answer 1

You have to touch each element, but don't count parents as a second action, make that part of iterating over them.

Each time you go down a level, increment a depth variable.

When you go up a level, compare your current depth to a saved "Deepest" variable. If it's greater, replace the "deepest" variable.

Of course when you go up a level you also decrement the depth variable...

This could EASILY be written functionally with a single recursive method that takes Node and returns deepest.

int maxDepth(Node node)
    int max=0;
    for each child of node
        thisMax=maxDepth(child)
        if(max < thisMax)
            max=thisMax
    return max+1

(This is one of those rare cases where you can write a recursive function without separating out the terminating clause)

Answer 2

Ass Bill K says, you'll need to do some searching yourself. What you can do is to reduce the search set by only looking at leaf-nodes, i.e. nodes that have an empty child axes:

//*[count(child::*) = 0]

You can then iterate over all the nodes returned by that expression and do

count(ancestor::*)

... and find the node for which that reaches the maximum.