Codecademy Logo

Binary Search Trees

Binary Search Tree - Methods

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

Binary Search Tree - General

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

Binary Search Tree - Insert Value

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

Binary Search Tree - Get Node By 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;
}
}

Binary Search Tree - In Order Depth-First Traversal

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

Learn More on Codecademy