finding height of a binary search tree without using recursion

[AceKnocks]

I have been given this interface,

interface BinarySearchTree {
   public void insert(Integer data);
   public int size();
   public int height();
   public boolean contains(Integer target);
}
 

and I have to implement BST with all these functions. I have implemented the first insert and size like this way -

class Node {
    Node left, right;
    Integer data;
    Node () {
        left = right = null;
        data = 0;
    }
}
 
public class BSTree extends Node implements BinarySearchTree {
    static Node root;
    static int countNode;
    /**
     * Creates a new instance of BSTree
     */
    public BSTree() {
        root = null;
    }
    public void insert(Integer data) {
        if (root == null) {
            root.data = data;
            countNode++;
        } else {
            Node temp = new Node();
            temp = root;
            while (temp != null) {
                if (temp.data < data) temp = temp.right;
                else {
                    temp = temp.left;
                }
                temp.data = data;
                countNode++;
            }
        }
    }
    public int size () {
        return countNode;
    }
 
    public int height() { 
        Node temp = new Node();
        /* could have used these for recursion 
        final boolean flag = true;
        if (flag) */
            temp = root;
        if (temp == null) {
            return 0;
        } else {
        /* would have been easy to find height using this recursion
            return 1 + max(height(temp.left), height(temp.right)); */
        }
    }
 
    public boolean contains (Integer target) {
 
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
 
        BSTree bs = new BSTree();
        bs.insert(12);
        bs.insert(3);
        bs.insert(14);
    }
 
}
 
 

The objective requires that the height be implemented without using an argument. Do you have some ideas?

[JosAH]

I must have been thinking of Ents

How silly: Ents are totally extinct because they were all male. You can use
final static variables for them.

kind regards,

Jos ;-)

[JosAH]

Maybe it's my background (math) but I usually find recursion easier to write and understand than iteration.

Let's shake hands but the way I read the question was about a non recursive
method and I'm also from the lazy bones camp and I think it's much easier
to cache stuff manipulated in the insert method than to set up explicit stacks
and/or trying to be clever with pointer fiddling etc. Recursive methods are much
easier to handle and implement though; I agree.

kind regards,

Jos

[BigDaddyLH]

Let's shake hands but the way I read the question was ...

Hear, hear. Now if we weren't on far sides of the world, I would say that calls for a beer!

[JosAH]

Hear, hear. Now if we weren't on far sides of the world, I would say that calls for a beer!

Me too! No problem though, distance is just a figment of people's imagination and
we can solve this the mathematical way: I buy and drink your beer as well ;-)

kind regards,

Jos

[r035198x]

Me too! No problem though, distance is just a figment of people's imagination and
we can solve this the mathematical way: I buy and drink your beer as well ;-)

kind regards,

Jos

Public drinking is not allowed in the public forums.
Admin.

[JosAH]

Public drinking is not allowed in the public forums.
Admin.

I wore a brown paper bag over my head so there was nothing public about it. I
looked and acted just like any other law obedient citizen.

kind regards,

Jos ;-)

[AceKnocks]

static Node root;
static int countNode;
...
 
public BSTree() {
    root = null;
}
...
public int size () {
    return countNode;
}
 
 

I just noticed that the root and the countNode (tree size) fields are static. What happens when you have another tree?

Those variables are static because trees themselves don't move either; when will
people ever learn ...

kind regards,

Jos ;-)

Thanks Jos for defending the objective. In this problem we were not assigned to make multiple BSTrees, rather just one tree which would have all these functions. :)

As far as writing a non-recursive (loop-iterative) height function is concerned, I could not come up with any and therefore implemented an overridden recursive function in the same class and called that recursive function from this non-recursive function.

I know that wasn't what I was supposed to do but I didnt have any bright ideas until the very last minute of my submission. Time for a compromise..eh

[BigDaddyLH]

Thanks Jos for defending the objective. In this problem we were not assigned to make multiple BSTrees, rather just one tree which would have all these functions. :)

I would rethink that, if I were you. You are going out of your way to make your code less general. If you insist on having static data, then all the methods should be made static, and the constructor hidden, because you've given up on a class that is designed to be instantiated.