Velocity Reviews > Java > tree structures

# tree structures

shawn
Guest
Posts: n/a

 03-07-2006
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.

Jacob
Guest
Posts: n/a

 03-07-2006
shawn wrote:

> 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

Matt Humphrey
Guest
Posts: n/a

 03-07-2006

"shawn" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> 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 http://www.velocityreviews.com/forums/(E-Mail Removed) http://www.iviz.com/

shawn
Guest
Posts: n/a

 03-07-2006
thanks guys