# tree structures

Discussion in 'Java' started by shawn, Mar 7, 2006.

1. ### shawnGuest

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.

shawn, Mar 7, 2006

2. ### JacobGuest

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

Jacob, Mar 7, 2006

3. ### Matt HumphreyGuest

"shawn" <> wrote in message
news:...
> 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.iviz.com/

Matt Humphrey, Mar 7, 2006
4. ### shawnGuest

thanks guys

shawn, Mar 7, 2006