Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Getting height of binary search tree without using recursion

1. ## 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?

```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;
}```

2. ## 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.

3. ## 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

nodes-in-binary-search-tree.png

4. ## 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.

5. ## Re: Getting height of binary search tree without using recursion

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:
```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));
}```

6. ## 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.

7. ## 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.

8. ## 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.

9. ## The Following User Says Thank You to Parranoia For This Useful Post:

berserker (November 8th, 2013)

10. ## Re: Getting height of binary search tree without using recursion

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!

11. ## Re: Getting height of binary search tree without using recursion

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