Thread: 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;
    }

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.

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

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.

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

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.

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.

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.

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!

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