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?

[BigDaddyLH]

Hint: methods are applied to objects. With your height method, you seem to only want to pass objects as arguments. Hmmm...

[Ganon11]

Most recursive methods dealing with trees can be written with some loops - try thinking of, in general, what your recursive calls would do, then try to mimic that with loops.

[BigDaddyLH]

Most recursive methods dealing with trees can be written with some loops - try thinking of, in general, what your recursive calls would do, then try to mimic that with loops.

I didn't see anywhere (other that the topic!) in the original post where the OP was required to write a height function that wasn't recursive, just one that worked!

[Ganon11]

Guess I read into that by the phrase "The objective requires that the height be implemented without using an argument." Most recursive functions have an argument, though I suppose you could implement the recursion without an argument. Then again, if you did so (at least the way I'm thinking) you may as well just use loops.

[JosAH]

@OP: you keep a separate variable countNode to keep track of the number of
nodes in the tree. You can do similar things where you keep track of the depth
or height of a node in the nodes themselves. At every insert you can update a
separate variable treeHeight and return its value at any time. That way you don't
need any recursion nor arguments to methods and what else ...

kind regards,

Jos

[BigDaddyLH]

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?

[BigDaddyLH]

@OP: you keep a separate variable countNode to keep track of the number of
nodes in the tree. You can do similar things where you keep track of the depth
or height of a node in the nodes themselves. At every insert you can update a
separate variable treeHeight and return its value at any time. That way you don't
need any recursion nor arguments to methods and what else ...

kind regards,

Jos

I'm from the compute-don't-cache school (of default behaviours). getSize is easy to write recursively (I hope this isn;t giving away the exercise!):

public int getSize () {
    return _size(root);
}
 
private static int _size(Node n) {
    return n==null? 0 : _size(n.left) + _size(n.right);
}

Method getHeight is just as easy to write recursively. (I think it's actually much harder to write iteratively, since it is not a simple tail recursion.)

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

[JosAH]

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

[BigDaddyLH]

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

kind regards,

Jos ;-)

I must have been thinking of Ents