tree structures

S

shawn

Does anyone know how to calculate the height of a tree structure? The
height should be for the maximum size branch. My tree is mad up with
nodes that have a getLeft and getRight method. getLeft and getRight
return the reference to the node in that position, or null if there
isnt one there.
 
J

Jacob

shawn said:
Does anyone know how to calculate the height of a tree structure? The
height should be for the maximum size branch. My tree is mad up with
nodes that have a getLeft and getRight method. getLeft and getRight
return the reference to the node in that position, or null if there
isnt one there.

Something like:

int getDepth(Node node, int depth)
{
int leftDepth = depth;
int rightDepth = depth;

if (node.getLeft())
leftDepth = getDepth(node.getLeft(), depth + 1);
if (node.getRight())
rightDepth = getDepth(node.getRight(), depth + 1);

return max(leftDepth, rightDepth);
}


Call by getDepth(root, 1)

NOT tested :)
 
M

Matt Humphrey

shawn said:
Does anyone know how to calculate the height of a tree structure? The
height should be for the maximum size branch. My tree is mad up with
nodes that have a getLeft and getRight method. getLeft and getRight
return the reference to the node in that position, or null if there
isnt one there.

int getHeight (Node node) {
if (node == null) return 0;

return 1 + Math.max (getHeight(node.getLeft()),
getHeight(node.getRight()));
}

getHeight (rootNode)

or implicitly as a method of Node

int getHeight () {
int leftHeight = getLeft() != null ? getLeft.getHeight() : 0;
int rightHeight = getRight () != null ? getRight.getHeight () : 0;

return 1 + Math.max (leftHeight, rightHeight);
}

rootNode.getHeight ()

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top