Skip to Content
Codecademy Logo

Binary Search Trees

Print Cheatsheet

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