Binary Search Tree - Java

Question

Hey guys i have problem with the depth(finding depth of the binary tree) and printTree(printing the tree in order). Here is my code.

import java.util.LinkedList;
import java.util.Queue;

public class BSTDictionary<T1, T2>{

private static class Node<T>{
    public Node<T> left;
    public Node<T> right;
    public T data;
    public Node(T data)
    {
        this.data = data;
    }
    public Node<T> getLeft()
    {
        return this.left;
    }
    public void setLeft(Node<T> left)
    {
        this.left = left;
    }
    public Node<T> getRight()
    {
        return this.right;
    }
    public void setRight(Node<T> right)
    {
        this.right = right;
    }
}

public int depth(Node root){

    if(root == null) {
        return 0;
    }
    else return 1 + Math.max((root.getLeft(), root.getRight());
}

public void printTree(){

    Node<?> n;
    Queue<Node<?>> nodequeue = new LinkedList<Node<?>>();
    while (!nodequeue.isEmpty())
    {
        Node<?> next = nodequeue.remove();
        System.out.print(next.data + " ");
        if (next.getLeft() != null)
        {
            nodequeue.add(next.getLeft());
        }
        if (next.getRight() != null)
        {
            nodequeue.add(next.getRight());
        }
    }}}

And here is the Test class that i am provided for testing these methods.

    public class DictionaryAdvancedTest {
protected static String[] entries = new String[26 * 26];

protected static void fill() {
    // Insert 26 * 26 entries
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++) {
            StringBuffer s = new StringBuffer();
            s.append((char) ((int) 'A' + i));
            s.append((char) ((int) 'A' + j));
            entries[i * 26 + j] = s.toString();
        }
} // fill method

public static void main(String[] args) {
    BSTDictionary<String, SortableString> dict1 = new BSTDictionary<String, SortableString>();
    AVLDictionary<String, SortableString> dict2 = new AVLDictionary<String, SortableString>();

    // Insert lots of entries
    fill();
    for (int i = 0; i < 26 * 26; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        dict1.insert(new SortableString(entries[e]), entries[e]);
        dict2.insert(new SortableString(entries[e]), entries[e]);
        entries[e] = null;
    }

    // print the two dictionaries
    dict1.printTree();
    dict2.printTree();
    // print the depth
    System.out.println("The initial BST tree has a maximum depth of "
            + dict1.depth());
    System.out.println("The initial AVL tree has a maximum depth of "
            + dict2.depth());

    // Delete half the entries
    fill();
    for (int i = 0; i < 13 * 26; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        dict1.delete(new SortableString(entries[e]));
        dict2.delete(new SortableString(entries[e]));
    }

    System.out
            .println("After deletes, the BST tree has a maximum depth of "
                    + dict1.depth());
    System.out
            .println("After deletes, the AVL tree has a maximum depth of "
                    + dict2.depth());

    // Add a quarter the entries
    fill();
    for (int i = 0; i < 6 * 26; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        dict1.insert(new SortableString(entries[e]), entries[e]);
        dict2.insert(new SortableString(entries[e]), entries[e]);
    }

    System.out
            .println("After insertions, the BST tree has a maximum depth of "
                    + dict1.depth());
    System.out
            .println("After insertions, the AVL tree has a maximum depth of "
                    + dict2.depth());

    // Search for a few random entries
    fill();
    for (int i = 0; i < 6; i++) {
        int e;
        do {
            e = (int) (Math.random() * (26 * 26));
        } while (entries[e] == null);

        System.out.print("Searching for " + entries[e] + ": ");
        if (dict1.search(new SortableString(entries[e])) == null) {
            System.out.print("Not found in Dict1, ");
        } else {
            System.out.print("Found in Dict1, ");
        }
        if (dict2.search(new SortableString(entries[e])) == null) {
            System.out.println("not found in Dict2.");
        } else {
            System.out.println("found in Dict2.");
        }
    }
}} 

Thank you guys :)

Answer 1

There is a compilation error at return 1 + Math.max((root.getLeft(), root.getRight());

There is an extra( and root.getLeft is returning node which is not of type int.

I am not sure how will you get the tree depth.. by getting only root.getLeft as it will only return the node to the left.As per my understanding we will need to get the number of nodes and then add 1 to it.

I am also trying to learn BST along with you..I will let you know, if i find anything else..If something is wrong in my understanding, you also please let me know.

Happy Learning!

Answer 2

public int depth(Node root){

if(root == null) {
    return 0;
}
else return 1 + Math.max((root.getLeft(), root.getRight());
}

Replace last line with else return 1 + Math.max(depth(root.getLeft()), depth(root.getRight()));

Rest of the messages are from search function which you didn't include in your question.