Binary Search Trees

To implement a BinarySearchTree class in Java, we need at least the following methods:

• an .insert() method that takes in a value and adds it to the tree
• a .getNodeByValue() method that takes in a value and returns the matching Binary Search Tree node
• a .depthFirstSearch() method that prints an in-order depth-first traversal of the tree

The Java implementation of the BinarySearchTree class should contain value and depth data and left and right pointers.

It has the following instance variables:

• int value, set to the value passed in to the constructor
• int depth, set to the depth passed in, or defaulted to 1 by the constructor
• BinarySearchTree left, set to null by the constructor
• BinarySearchTree right, set to null by the constructor

The BinarySearchTree Java class has an .insert() method that takes in a value and uses recursion to add a new node to the tree while maintaining the binary tree property. It returns nothing.

The code looks like this:

public void insert(int value) {
   if (value < this.value) {
     if (this.left == null) {
       this.left = new BinarySearchTree(value, this.depth + 1);
     } else {
       this.left.insert(value);
     }
   } else {
     if (this.right == null) {
       this.right = new BinarySearchTree(value, this.depth + 1);
     } else {
       this.right.insert(value);
     }
   }
 }

The BinarySearchTree Java class has a .getNodeByValue() instance method that takes in a value and returns the corresponding BinarySearchTree node, or null if it doesn’t exist. The method uses recursion to search through the sides of the tree.

The code looks like this:

public BinarySearchTree getNodeByValue(int value) {
   if (this.value == value) {
     return this;
   } else if (value < this.value && this.left != null) {
     return this.left.getNodeByValue(value);
   } else if (value >= this.value && this.right != null) {
     return this.right.getNodeByValue(value);
   } else {
     return null;
   }
}

The BinaryTree Java class has a .depthFirstTraversal() instance method that prints the in-order depth-first traversal of the tree.

In-order traversal requires visiting the left child first, the current tree node next, and then the right child. There are also pre-order and post-order traversal methods that visit these in a different sequence.

The output of an in-order traversal will always be in ascending order. Our depth-first in-order traversal method takes no variables and returns nothing.

The code looks like this:

public void depthFirstTraversal() {
  if (this.left != null) {
    this.left.depthFirstTraversal();
  }
  System.out.println(this.value);
  if (this.right != null) {
    this.right.depthFirstTraversal();
  }
}