Binary Trees in Java

Introduction

Binary search tree (BST) is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

From the above properties, it naturally follows that each node (item in the tree) has a distinct key. Generally, the information represented by each node is an Object element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Using the Code

As said in the introduction, every node has left and right nodes. Below is how a node should look like:

public class BNode {

    public BNode leftBNode,  rightBNode; // the nodes
    public AnyClass anyClass; //the AnyClass objext

    public BNode(AnyClass anyClass ) {//constructor
        this.anyClass= anyClass;
        this.leftBNode = null;
        this.rightBNode = null;
    }

    public void show() {
        //calls the show method of the AnyClass
        System.out.print(anyClass.show());
    }
}

Below is a simple class that traverses, adds, and searches for a particular node value:

public class BinTree {
    BNode theBTRootNode;

    public BinTree() // constructor
    {
        theBTRootNode = null;
    }

    // ------------------ Addition of the node to the BST-------------------
    protected BNode insertAB(BNode theRootNode, BNode myNewNode) {
        if (theRootNode == null) {
            theRootNode = myNewNode;
            //checks if the username is smaller than 
            //the root object, if smaller appends to the left
        } else if (myNewNode.anyClass.surname.compareTo(
                          theRootNode.anyClass.surname) < 0) {
            theRootNode.leftBNode = insertAB(theRootNode.leftBNode, myNewNode);
        } else {
            // else if bigger appends to the right
            theRootNode.rightBNode = 
               insertAB(theRootNode.rightBNode, myNewNode);
        }
        return theRootNode;
    }

    public void insertBST(AnyClass anyClass) {
        BNode anyClassBTNode = new BNode(anyClass);
        //calls insert above
        theBTRootNode = insertAB(theBTRootNode, anyClassBTNode);
    }

    // ------------------ InOrder traversal-------------------
    protected void inorder(BNode theRootNode) {
        if (theRootNode != null) {
            inorder(theRootNode.leftBNode);
            theRootNode.show();
            inorder(theRootNode.rightBNode);
        }
    }

    //calls the method to do in order
    public void inorderBST() {
        inorder(theBTRootNode);
    }

    // ----- Search for key name and  returns ref. 
    //              to BNode or null if not found--------
    protected BNode search(BNode theRootNode, String keyName) {
        //if the root is null returns null
        if (theRootNode == null) {
            return null;
        } else {
            //checks if they are equal
            if (keyName.compareTo(theRootNode.anyClass.surname) == 0) {
                return theRootNode;
            //checks id the key is smaller than the current
            //record  if smaller traverses to the left
            } else if (keyName.compareTo(theRootNode.anyClass.surname) < 0) {
                return search(theRootNode.leftBNode, keyName);
            } else {
                // if bigger traverses to the left
                return search(theRootNode.rightBNode, keyName);
            }
        }
    }

    //returns null if no result else returns 
    //the AnyClass object matched with the keyName
    public AnyClass searchBST(String keyName) {
        BNode temp = search(theBTRootNode, keyName);
        if (temp == null) {
      //noresults found
           return null;
        } else {
         //result found
           return temp.anyClass;
        }
    }
}

Points of Interest

This should help you a lot in achieving faster applications when traversing through a list.

You can add this method to the BinTree class object to transfer your lists to a binary tree:

public void populateBinTree(List theList) {
    //clearing the root as not to append, 
    //if you want to append just remove the below line
    theBTRootNode = null;
   //keeps looping untill reaches the end of the list
    for(int i = 0;i < theList.size();i++)
            Node temporaryNode = null; 
         //inserts in the BST
        insertBST((AnyClass)theList.get(i));
        //goes to the next element
    }
}

History

• Initial version.