# Getting height of binary search tree without using recursion

• November 7th, 2013, 10:49 PM
berserker
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; }```
• November 7th, 2013, 11:30 PM
Parranoia
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.
• November 7th, 2013, 11:33 PM
berserker
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
• November 7th, 2013, 11:42 PM
Parranoia
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.
• November 7th, 2013, 11:48 PM
berserker
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)); }```
• November 7th, 2013, 11:52 PM
Parranoia
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.
• November 8th, 2013, 12:00 AM
berserker
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.
• November 8th, 2013, 12:05 AM
Parranoia
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.
• November 8th, 2013, 12:07 AM
berserker
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:
• November 8th, 2013, 12:37 AM
Parranoia
Re: Getting height of binary search tree without using recursion
No problem. Always helps to have someone else to talk a problem through.