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, next;
    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 purposes
        final boolean flag = true;
        if (flag) */
            temp = root;
        if (temp == null) {
            return 0;
        } else {
                /* would have been easy to find the height with recursion in the following way
            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?

For starters, I'll state that I'm not exactly sure what the 'height' of a b-tree represents. My guess is the number of nodes and any visible children nodes. If so, then here's my thought:

User the root node, assign its size to a variable, then start a while loop. When you come across an expanded node, throw the current root node onto a stack, readjust the size variable, and continue on. Last line in the while loop should be a check to see if the current index equals 0, then if so check if anything is on the stack and reassign the next root node accordingly.

At least this is the idea I've come up with in my head. Let me know how you worked this out.

>For starters, I'll state that I'm not exactly sure what the 'height' of a b-tree represents.
The height of a binary search tree is the number of nodes in the longest path to a leaf.

>Do you have some ideas?
Without recursion you're basically looking at simulated recursion using a stack. In particular, it would be most like a postorder traversal.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.