Getting height of binary search tree without using recursion

Hello. I'm stuck on a homework problem and could use some help if someone would be so kind as to help a beginner understand Java. I'm having some trouble trying to get the height of a binary search tree without relying on recursion. I've created a instance field called h to the Node class and I'm supposed to add a statement to the put method below to update the height after inserting a Node object. Can someone help me to understand how I'm supposed to do this?

Code java:

public void put(Key key, Value val) {
if (val == null) {
delete(key);
return;
}
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
x.N = 1 + size(x.left) + size(x.right);
return x;
}

Re: Getting height of binary search tree without using recursion

Well, since you added the h field, you should first initialize it to 0 when the tree is first created. Then once a node is added to the tree, increment the height by one. When a node is removed, decrease the height by one.

1 Attachment(s)

Re: Getting height of binary search tree without using recursion

But wouldn't that just give me the total number of nodes? The height is not the same as the total number of nodes. It's the longest path from the root to any child node.

For instance for the binary search tree below, the height would be 3

Attachment 2458

Re: Getting height of binary search tree without using recursion

Ohhh, gotcha. Height, not size.

Were you told whether or not the tree is balanced? If it must be balanced then this could be done a bit easier. If not, I'm not too sure I have a solution right off.

Re: Getting height of binary search tree without using recursion

Quote:

Originally Posted by

**Parranoia**
Ohhh, gotcha. Height, not size.

Were you told whether or not the tree is balanced? If it must be balanced then this could be done a bit easier. If not, I'm not too sure I have a solution right off.

The tree can be unbalanced. The easiest way to do it would be through recursion like below but we aren't allowed to do it that way:

Code java:

public int height() {
return height(root);
}
private int height(Node x) {
if (x == null) {
return -1;
}
return 1 + Math.max(height(x.left), height(x.right));
}

Re: Getting height of binary search tree without using recursion

Okay, so after thinking for a bit I might have some insight.

When you add a node, add 1 to the parent's height. This effect should give the bottom row a height of 0 (or 1 depending on how you're counting) and the root node's height would be the height of the tree.

Hopefully this makes sense. It's been bouncing around in my head for a bit.

Re: Getting height of binary search tree without using recursion

You're close. However, a node can have two children. So, say for instance that you add a left child; you would then add 1 to the height of it's parent. But, then if you add a right child, you'd add another 1 to the height of the parent, which would be wrong since you've only gone one level down but you added 2 to the height of the parent.

Re: Getting height of binary search tree without using recursion

I knew there had to be something wrong with it. Perhaps you could check if it's the first node being added to the parent before adding to the height.

So if the parent already has one child, don't add to the height. If it has zero children, add to the height.

Re: Getting height of binary search tree without using recursion

Quote:

Originally Posted by

**Parranoia**
I knew there had to be something wrong with it. Perhaps you could check if it's the first node being added to the parent before adding to the height.

So if the parent already has one child, don't add to the height. If it has zero children, add to the height.

Yes, I think that's the proper strategy. I'll see if I can write out the code and if it works I'll post it here for other users to benefit from. Thanks for your help by the way! :cool:

Re: Getting height of binary search tree without using recursion

No problem. Always helps to have someone else to talk a problem through.