re: Recursion, Part Six: Making CPS Work

PiersH — Sat, 10 Nov 2007 20:21:13 GMT

great series, eric. here's a stack-based solution that doesn't use parent/sibling pointers or pointer rotations:

int treeDepth (Node node)

{

int depth = 0;

Stack<Node> rest = new Stack<Node> ();

while (node != null)

{

while (node != null)

{

rest.Push (node.right);

node = node.left;

}

depth = Math.Max (depth, rest.Count);

while (rest.Count > 0 && (node = rest.Pop ()) == null)

;

rest.Push (null);

}

return depth;

}

re: Recursion, Part Six: Making CPS Work

Patrick Geiller — Thu, 18 Aug 2005 00:32:42 GMT

I'll push the recursion stack ! If your tree nodes are well connected (eg pointers to sibling, parent) you can walk them in a single loop, without recursion.

In javascript :

function nodeMaxDepth(startNode)
{
var depth = 0, maxDepth = 0
var node = startNode
while (node)
{
if (node.firstChild)
{
node = node.firstChild
depth++
maxDepth = Math.max(depth, maxDepth)
}
while (node)
{
if (node == startNode) return maxDepth
if (node.nextSibling)
{
node = node.nextSibling
break
}
node = node.parentNode
depth--
}
}
}
alert(nodeMaxDepth(document.body))

Much easier ;)