Core Java

Binary Search Tree Java Example

Photo of Mary Zheng Mary ZhengJune 21st, 2019Last Updated: May 15th, 2020
0 294 22 minutes read

In this post, we feature a comprehensive Binary Search Tree Java Example.

1. Introduction

A binary tree is a recursive data structure where each node can have at most two children. A Binary Search Tree (BST) is a special type of binary tree which has the following properties:

  • The left sub-tree of a node contains the nodes with the key’s value lesser than itself.
  • The right sub-tree of a node contains the nodes with the key’s value greater than itself.
  • The left and right sub-trees each must also be a binary search tree.
  • There must be no duplicate nodes.

Binary Search Tree is used commonly in search applications where data is constantly adding or removing. In this example, I will demonstrate how to:

  • Define a Binary Search Tree data structure
  • Traverse Binary Search Tree nodes
  • Add a key in a Binary Search Tree
  • Delete a key from a Binary Search Tree
  • Search a key in a Binary Search Tree

2. Technologies Used

The example code in this article was built and run using:

  • Java 11
  • Maven 3.3.9
  • Eclipse Oxygen
  • Junit 4.12
  • LogBack 1.2.3

3. Maven Project

In this step, I will create a Maven project which includes several classes:

  • BinaryNode – defines a data structure for a binary node.
  • BinarySearchTree – defines a data structure for a binary search tree.
  • TraverseService – traverses with pre-order, in-order, post-order, and level-order .
  • InsertService – inserts a new key.
  • DeleteService – deletes a key.
  • SearchService – searches a key.
Figure 1 Class Diagram

3.1 POM.XML

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
  <modelVersion>4.0.0</modelVersion>
  <groupId>jcg-zheng-bst-demo</groupId>
  <artifactId>jcg-zheng-bst-demo</artifactId>
  <version>0.0.1-SNAPSHOT</version>
  <build>
    <sourceDirectory>src</sourceDirectory>
    <plugins>
      <plugin>
        <artifactId>maven-compiler-plugin</artifactId>
        <version>3.8.0</version>
        <configuration>
          <release>11</release>
        </configuration>
      </plugin>
    </plugins>
  </build>
  <dependencies>
   <dependency>
   <groupId>junit</groupId>
   <artifactId>junit</artifactId>
   <version>4.12</version>
   </dependency>
<dependency>
			<groupId>ch.qos.logback</groupId>
			<artifactId>logback-access</artifactId>
			<version>1.2.3</version>
		</dependency>
		<dependency>
			<groupId>ch.qos.logback</groupId>
			<artifactId>logback-classic</artifactId>
			<version>1.2.3</version>
		</dependency>
		<dependency>
			<groupId>ch.qos.logback</groupId>
			<artifactId>logback-core</artifactId>
			<version>1.2.3</version>
		</dependency>
  </dependencies>
</project>

3.2 BinaryNode

A binary node is a data structure which consists with a key value and left and right children nodes. The top-most node is called root. A node without any child is called a leaf node. In this step, I will create a BinaryNode class which defines a node with three data members:

  • keyValue – an integer for the key value
  • left – a BinaryNode whose key value is less than its key value
  • right – a BinaryNode whose key value is greater than its key value

It also includes getter, setter, toString, equals, and hashcode methods.

BinaryNode.java

package jcg.zheng.demo.bst;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * A binary tree is a data structure which each node can have at most 2
 * children.
 *
 */
public class BinaryNode {
	private int keyValue;
	private BinaryNode left;
	private final Logger logger = LoggerFactory.getLogger(this.getClass());
	private BinaryNode right;

	public BinaryNode(final int value) {
		super();
		this.keyValue = value;
		this.left = null;
		this.right = null;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		BinaryNode other = (BinaryNode) obj;
		if (keyValue != other.keyValue)
			return false;
		if (left == null) {
			if (other.left != null)
				return false;
		} else if (!left.equals(other.left))
			return false;
		if (right == null) {
			if (other.right != null)
				return false;
		} else if (!right.equals(other.right))
			return false;
		return true;
	}

	public int getKeyValue() {
		return keyValue;
	}

	public BinaryNode getLeft() {
		return left;
	}

	public BinaryNode getRight() {
		return right;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + keyValue;
		result = prime * result + ((left == null) ? 0 : left.hashCode());
		result = prime * result + ((right == null) ? 0 : right.hashCode());
		return result;
	}

	public void setKeyValue(final int value) {
		if (value != this.keyValue) {
			logger.info("Node:{} has a new key value {}", this.toString(), value);
			this.keyValue = value;
		}
	}

	public void setLeft(final BinaryNode left) {
		if (left == null) {
			this.left = null;
		} else if (!left.equals(getLeft())) {
			logger.info("Node:{} sets new left_node:{}", this.toString(), (left == null ? null : left.toString()));
			this.left = left;
		}
	}

	public void setRight(final BinaryNode right) {
		if (right == null) {
			this.right = null;
		} else if (!right.equals(getRight())) {
			logger.info("Node:{} sets new right_node:{}", this.toString(), (right == null ? null : right.toString()));
			this.right = right;
		}
	}

	@Override
	public String toString() {
		return "BinaryNode [keyValue=" + keyValue + ", left=" + left + ", right=" + right + "]";
	}

}

3.3 InsertService

When inserting a key into a BST, the key is always added as a leaf node. In this step, I will create an InsertService class which finds the the right leaf node and set the newly added leaf node as its left or right child.

  • add(BinaryNode, int) – adds a new leaf node in a BST in the right position .

InsertService.java

package jcg.zheng.demo.bst;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class InsertService {

	private final Logger logger = LoggerFactory.getLogger(this.getClass());

	public BinaryNode add(final BinaryNode treeRoot, final int addingValue) {
		if (treeRoot == null) {
			logger.info("Create a new leaf node with keyvalue:{} ", addingValue);
			return new BinaryNode(addingValue);
		}

		if (addingValue < treeRoot.getKeyValue()) {
			treeRoot.setLeft(add(treeRoot.getLeft(), addingValue));
		} else if (addingValue == treeRoot.getKeyValue()) {
			return treeRoot;
		} else {
			treeRoot.setRight(add(treeRoot.getRight(), addingValue));
		}

		return treeRoot;
	}

}

3.4 SearchService

In this step, I will create a SearchService class which searches a key in a Binary Search Tree:

  • search(BinarNode, int) – searches the key by starting from the root. It returns root if its key value matching the given value, else it compares to root‘s left node if the searching value is less than root , otherwise it compares to root‘s right node.
  • findMaxKey – traverses the nodes to find the maximum key.
  • findMinKey – traverses the nodes to find the minimum key.

SearchNodeService.java

package jcg.zheng.demo.bst;

public class SearchService {

	public BinaryNode search(final BinaryNode treeRoot, final int findingValue) {
		if (treeRoot == null) {
			return null;
		}

		if (findingValue == treeRoot.getKeyValue()) {
			return treeRoot;
		} else if (findingValue > treeRoot.getKeyValue()) {
			return search(treeRoot.getRight(), findingValue);
		} else {
			return search(treeRoot.getLeft(), findingValue);
		}

	}

	public Integer findMaxKey(final BinaryNode root) {
		return root.getRight() == null ? root.getKeyValue() : findMaxKey(root.getRight());
	}

	public int findMinKey(final BinaryNode root) {
		return root.getLeft() == null ? root.getKeyValue() : findMinKey(root.getLeft());
	}
}

3.5 DeleteService

There are three different use cases when deleting a key from a BST:

  • The node-to-be-deleted is a leaf node – It just removes it from the tree.
  • The node-to-be-deleted has only one child – It replaces it by its child.
  • The node-to-be-deleted has two children – It first finds the node-to-be-deleted, then replaces it with its smallest right child node.

In this step, I will create a DeleteService class which deletes the given key.

  • delete(BinaryNode, int) – delete the node-to-be-deleted by finding it, and then removes it by setting it as null or replacing it with other node.

DeleteService.java

package jcg.zheng.demo.bst;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class DeleteService {
	private final Logger logger = LoggerFactory.getLogger(this.getClass());
	private SearchService searchService = new SearchService();

	public BinaryNode delete(final BinaryNode treeRoot, final int deletingValue) {
		if (treeRoot == null) {
			logger.info("delete return null for {}", deletingValue);
			return null;
		}

		if (deletingValue == treeRoot.getKeyValue()) {
			logger.info("found the deleting node{}", treeRoot.toString());
			if (treeRoot.getLeft() == null) {
				if (treeRoot.getRight() == null) {
					// delete the leaf node
					logger.info("return null because the to-be-delete node {} is a leaf node", deletingValue);
					return null;
				} else {
					// only right child
					logger.info("return the right node because the to-be-delete node {} has right child node",
							deletingValue);
					return treeRoot.getRight();
				}
			} else {
				if (treeRoot.getRight() == null) {
					// only Left child
					logger.info("return the left node because the to-be-delete node {} has left child node",
							deletingValue);
					return treeRoot.getLeft();
				} else {
					// has both children
					int min = searchService.findMinKey(treeRoot.getRight());
					logger.info("Replace key with with the minumu value {} and reset the right node", min);
					treeRoot.setKeyValue(min);
					treeRoot.setRight(delete(treeRoot.getRight(), min));
					return treeRoot;
				}

			}
		} else if (deletingValue < treeRoot.getKeyValue()) {
			BinaryNode temp = delete(treeRoot.getLeft(), deletingValue);
			if (temp == null || (treeRoot.getLeft() != null && !treeRoot.getLeft().equals(temp))) {
				treeRoot.setLeft(temp);
			}
			return treeRoot;
		} else {
			BinaryNode temp = delete(treeRoot.getRight(), deletingValue);
			treeRoot.setRight(temp);
			return treeRoot;
		}

	}

}

3.6 BinarySearchTree

In this step, I will create a BinarySearchTree class which has a root node and several methods:

  • add(int) – adds a new leaf node with the given value.
  • delete(int) – deletes the node with the matching key value.
  • searchNode(int) – searches the node in a BinarySearchTree for the matching key value.
  • max() – finds the maximum key value.
  • min() – finds the minimum key value.

BinarySearchTree.java

package jcg.zheng.demo.bst;

/**
 * A Binary search tree is a specific binary tree in which the left side node's
 * value is smaller than the root's value and the right side node's value is
 * greater than the root's value
 *
 */
public class BinarySearchTree {

	private BinaryNode root;

	private InsertService insertSerivce = new InsertService();

	private DeleteService deleteService = new DeleteService();

	private SearchService searchService = new SearchService();

	public void add(final int value) {
		root = insertSerivce.add(root, value);
	}

	public void delete(final int deletingValue) {
		root = deleteService.delete(root, deletingValue);
	}

	public BinaryNode getRoot() {
		return root;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public int max() {
		return searchService.findMaxKey(root);
	}

	public int min() {
		return searchService.findMinKey(root);
	}

	public BinaryNode searchKey(final int findingValue) {
		return searchService.search(root, findingValue);
	}

	@Override
	public String toString() {
		return "BinarySearchTree [root=" + root + "]";
	}

}

3.7 TraverseService

In this step, I will create a TraverseService class which traverses nodes in a Binary Search Tree in four ways:

  • levelOrder – traverses the nodes in BST based on the level.
  • inOrder – traverses the nodes in BST based on the depth in left, root, right order. It provides a sorted list.
  • preOrder – traverses the nodes in BST based on the depth in root, left, right order. It keeps the insertion order.
  • postOrder – traverses the nodes in BST based on the depth in left, right, root order.

TraverseService.java

package jcg.zheng.demo.bst;

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

public class TraverseService {

	public void inOrder_sorted(final BinaryNode root) {
		if (root != null) {
			inOrder_sorted(root.getLeft());
			print(root);
			inOrder_sorted(root.getRight());
		}

	}

	public void levelOrder(final BinaryNode root) {

		Queue<BinaryNode> fifo = new LinkedList<>();
		if (root == null) {
			return;
		}
		fifo.add(root);
		while (!fifo.isEmpty()) {
			BinaryNode tmpNode = fifo.remove();
			if (tmpNode.getLeft() != null) {
				fifo.add(tmpNode.getLeft());
			}
			if (tmpNode.getRight() != null) {
				fifo.add(tmpNode.getRight());
			}
			print(tmpNode);
		}
	}

	public void postOrder(final BinaryNode root) {
		if (root != null) {
			preOrder(root.getLeft());
			preOrder(root.getRight());
			print(root);
		}
	}

	public void preOrder(final BinaryNode root) {
		if (root != null) {
			print(root);
			preOrder(root.getLeft());
			preOrder(root.getRight());
		}

	}

	private void print(final BinaryNode root) {
		System.out.print(root.getKeyValue() + " ");
	}

}

4. Test Classes

4.1 BinaryNodeTest

In this step, I will create a BinaryNodeTest class which tests a leaf node, a node with left-child, a node with right-child, and a node with both left and right children.

BinaryNodeTest.java

package jcg.zheng.demo.bst;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;

import org.junit.Test;

public class BinaryNodeTest {
	BinaryNode binaryNode = new BinaryNode(1);

	@Test
	public void test_leaf_node() {
		assertEquals(1, binaryNode.getKeyValue());
		assertNull(binaryNode.getLeft());
		assertNull(binaryNode.getRight());
		System.out.println(binaryNode.toString());
	}

	
	@Test
	public void test_has_left_node() {
		binaryNode.setLeft(new BinaryNode(0));
		assertEquals(1, binaryNode.getKeyValue());
		assertNotNull(binaryNode.getLeft());
		assertEquals(0, binaryNode.getLeft().getKeyValue());
		System.out.println(binaryNode.toString());
	}
	
	@Test
	public void test_has_right_node() {
		binaryNode.setRight(new BinaryNode(3));
		assertEquals(1, binaryNode.getKeyValue());
		assertNotNull(binaryNode.getRight());
		assertEquals(3, binaryNode.getRight().getKeyValue());
		System.out.println(binaryNode.toString());
	}
	
	@Test
	public void test_has_two_nodes() {
		binaryNode.setLeft(new BinaryNode(0));
		binaryNode.setRight(new BinaryNode(3));
		assertEquals(0, binaryNode.getLeft().getKeyValue());
		assertEquals(3, binaryNode.getRight().getKeyValue());
		System.out.println(binaryNode.toString());
	}
}

Execute the test and capture the output here.

Output

Running jcg.zheng.demo.bst.BinaryNodeTest
21:14:33.011 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=1, left=null, right=null] sets new left_node:BinaryNode [keyValue=0, left=null, right=null]
BinaryNode [keyValue=1, left=BinaryNode [keyValue=0, left=null, right=null], right=null]
21:14:33.025 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=1, left=null, right=null] sets new right_node:BinaryNode [keyValue=3, left=null, right=null]
BinaryNode [keyValue=1, left=null, right=BinaryNode [keyValue=3, left=null, right=null]]
21:14:33.026 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=1, left=null, right=null] sets new left_node:BinaryNode [keyValue=0, left=null, right=null]
21:14:33.026 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=1, left=BinaryNode [keyValue=0, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=3, left=null, right=null]
BinaryNode [keyValue=1, left=BinaryNode [keyValue=0, left=null, right=null], right=BinaryNode [keyValue=3, left=null, right=null]]
BinaryNode [keyValue=1, left=null, right=null]
Tests run: 4, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.422 sec

Results :

Tests run: 4, Failures: 0, Errors: 0, Skipped: 0

4.2 TestBase

In this step, I will create a TestBase class which has common methods to display each test method’s name.

TestBase.java

package jcg.zheng.demo.bst;

import static org.junit.Assert.assertTrue;

import org.junit.After;
import org.junit.Before;
import org.junit.Rule;
import org.junit.rules.TestName;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class TestBase {
	protected BinarySearchTree bst = new BinarySearchTree();
	protected final Logger logger = LoggerFactory.getLogger(this.getClass());

	protected DeleteService deleteSerice = new DeleteService();

	protected SearchService searchService = new SearchService();

	protected InsertService insertService = new InsertService();

	@Rule
	public TestName testName = new TestName();

	@Before
	public void setup() {
		assertTrue(bst.isEmpty());
		logger.info("Start {}", testName.getMethodName());
	}

	@After
	public void cleanup() {
		logger.info("End {}", testName.getMethodName());
	}
}

4.3 SearchServiceTest

In this step, I will create a SearchServiceTest class which tests add, searchNode, findMinKey, and findMaxKey methods.

SearchServiceTest.java

package jcg.zheng.demo.bst;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;

import org.junit.Test;

public class SearchServiceTest extends TestBase {

	@Test
	public void test_search_node() {
		BinaryNode root = insertService.add(null, 6);

		insertService.add(root, 4);
		insertService.add(root, 2);
		insertService.add(root, 10);

		BinaryNode found12 = searchService.search(root, 22);
		assertNull(found12);

		BinaryNode found2 = searchService.search(root, 2);
		assertNotNull(found2);
		assertEquals(2, found2.getKeyValue());

		int max = searchService.findMaxKey(root);
		assertEquals(10, max);

		int min = searchService.findMinKey(root);
		assertEquals(2, min);

	}

}

Execute the test and capture the output here.

Output

Running jcg.zheng.demo.bst.SearchServiceTest
21:16:59.266 [main] INFO jcg.zheng.demo.bst.SearchServiceTest - Start test_search_node
21:16:59.276 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:16:59.278 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:16:59.343 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:16:59.343 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:16:59.343 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:16:59.343 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:16:59.344 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:16:59.345 [main] INFO jcg.zheng.demo.bst.SearchServiceTest - End test_search_node
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.442 sec

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0
  • line 5 – root node (6) has a left node (4).
  • line 7 – root’s left node (4) has a left node (2).
  • line 9 – root node (6) has a right node (10).

4.4 InsertServiceTest

In this step, I will create an InsertServiceTreeTest class which tests add method.

InsertServiceTest.java

package jcg.zheng.demo.bst;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class InsertServiceTest extends TestBase {

 
	@Test
	public void test_add_4_nodes() {
		BinaryNode root = insertService.add(null, 6);
		assertEquals(6, root.getKeyValue());

		insertService.add(root, 4);
		assertEquals(4, root.getLeft().getKeyValue());

		insertService.add(root, 2);
		assertEquals(2, root.getLeft().getLeft().getKeyValue());

		insertService.add(root, 10);
		assertEquals(10, root.getRight().getKeyValue());

	}

}

Execute the test and capture the output here.

Output

Running jcg.zheng.demo.bst.InsertServiceTest
21:18:31.211 [main] INFO jcg.zheng.demo.bst.InsertServiceTest - Start test_add_4_nodes
21:18:31.219 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:18:31.221 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:18:31.289 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:18:31.289 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:18:31.289 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:18:31.289 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:18:31.290 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:18:31.291 [main] INFO jcg.zheng.demo.bst.InsertServiceTest - End test_add_4_nodes
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.442 sec

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0

4.5 DeleteServiceTest

In this step, I will create a DeleteServiceTest class.

DeleteServiceTest.java

package jcg.zheng.demo.bst;

import static org.junit.Assert.assertNull;

import org.junit.Test;

public class DeleteServiceTest extends TestBase {
	

	@Test
	public void test_delete_left_leaf_node() {
		BinaryNode root = insertService.add(null, 6);

		insertService.add(root, 4);
		insertService.add(root, 2);
		insertService.add(root, 10);
		deleteSerice.delete(root, 2);
		
		BinaryNode found2 = searchService.search(root, 2);
		assertNull(found2);
	}
	
	@Test
	public void test_delete_right_leaf_node() {
		BinaryNode root = insertService.add(null, 6);

		insertService.add(root, 4);
		insertService.add(root, 2);
		insertService.add(root, 10);
		deleteSerice.delete(root, 10);
		
		BinaryNode found10 = searchService.search(root, 10);
		assertNull(found10);
	}
	
	@Test
	public void test_delete_left_subtree_node() {
		BinaryNode root = insertService.add(null, 6);

		insertService.add(root, 4);
		insertService.add(root, 2);
		insertService.add(root, 10);
		deleteSerice.delete(root, 4);
		
		BinaryNode found4 = searchService.search(root, 4);
		assertNull(found4);
	}
	
	@Test
	public void test_delete_right_subtree_node() {
		BinaryNode root = insertService.add(null, 6);

		insertService.add(root, 4);
		insertService.add(root, 2);
		insertService.add(root, 10);
		insertService.add(root, 8);
		deleteSerice.delete(root, 10);
		
		BinaryNode found10 = searchService.search(root, 10);
		assertNull(found10);
	}
	
	@Test
	public void test_delete_full_subtree_node() {
		BinaryNode root = insertService.add(null, 6);

		insertService.add(root, 4);
		insertService.add(root, 2);
		insertService.add(root, 10);
		insertService.add(root, 8);
		insertService.add(root, 11);
		deleteSerice.delete(root, 10);
		
		BinaryNode found10 = searchService.search(root, 10);
		assertNull(found10);
	}

}

Execute the test and capture the output here.

Output

Running jcg.zheng.demo.bst.DeleteServiceTest
21:19:46.623 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - Start test_delete_left_subtree_node
21:19:46.630 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:19:46.633 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:19:46.697 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:19:46.697 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:19:46.697 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:19:46.698 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:19:46.701 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:19:46.701 [main] INFO jcg.zheng.demo.bst.DeleteService - found the deleting nodeBinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null]
21:19:46.702 [main] INFO jcg.zheng.demo.bst.DeleteService - return the left node because the to-be-delete node 4 has left child node
21:19:46.702 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=BinaryNode [keyValue=10, left=null, right=null]] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:19:46.703 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - End test_delete_left_subtree_node
21:19:46.710 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - Start test_delete_full_subtree_node
21:19:46.710 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:19:46.710 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:19:46.711 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:19:46.712 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:19:46.712 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:19:46.712 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:19:46.713 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:19:46.713 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:8
21:19:46.714 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=10, left=null, right=null] sets new left_node:BinaryNode [keyValue=8, left=null, right=null]
21:19:46.714 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:11
21:19:46.714 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=10, left=BinaryNode [keyValue=8, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=11, left=null, right=null]
21:19:46.715 [main] INFO jcg.zheng.demo.bst.DeleteService - found the deleting nodeBinaryNode [keyValue=10, left=BinaryNode [keyValue=8, left=null, right=null], right=BinaryNode [keyValue=11, left=null, right=null]]
21:19:46.717 [main] INFO jcg.zheng.demo.bst.DeleteService - Replace key with with the minumu value 11 and reset the right node
21:19:46.717 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=10, left=BinaryNode [keyValue=8, left=null, right=null], right=BinaryNode [keyValue=11, left=null, right=null]] has a new key value 11
21:19:46.718 [main] INFO jcg.zheng.demo.bst.DeleteService - found the deleting nodeBinaryNode [keyValue=11, left=null, right=null]
21:19:46.718 [main] INFO jcg.zheng.demo.bst.DeleteService - return null because the to-be-delete node 11 is a leaf node
21:19:46.718 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - End test_delete_full_subtree_node
21:19:46.720 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - Start test_delete_right_leaf_node
21:19:46.720 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:19:46.721 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:19:46.721 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:19:46.721 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:19:46.721 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:19:46.721 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:19:46.722 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:19:46.722 [main] INFO jcg.zheng.demo.bst.DeleteService - found the deleting nodeBinaryNode [keyValue=10, left=null, right=null]
21:19:46.722 [main] INFO jcg.zheng.demo.bst.DeleteService - return null because the to-be-delete node 10 is a leaf node
21:19:46.723 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - End test_delete_right_leaf_node
21:19:46.726 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - Start test_delete_right_subtree_node
21:19:46.726 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:19:46.727 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:19:46.728 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:19:46.729 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:19:46.729 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:19:46.730 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:19:46.730 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:19:46.730 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:8
21:19:46.731 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=10, left=null, right=null] sets new left_node:BinaryNode [keyValue=8, left=null, right=null]
21:19:46.731 [main] INFO jcg.zheng.demo.bst.DeleteService - found the deleting nodeBinaryNode [keyValue=10, left=BinaryNode [keyValue=8, left=null, right=null], right=null]
21:19:46.733 [main] INFO jcg.zheng.demo.bst.DeleteService - return the left node because the to-be-delete node 10 has left child node
21:19:46.735 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=BinaryNode [keyValue=10, left=BinaryNode [keyValue=8, left=null, right=null], right=null]] sets new right_node:BinaryNode [keyValue=8, left=null, right=null]
21:19:46.736 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - End test_delete_right_subtree_node
21:19:46.738 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - Start test_delete_left_leaf_node
21:19:46.738 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:19:46.739 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:19:46.741 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:19:46.742 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:19:46.742 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:19:46.742 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:19:46.743 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=BinaryNode [keyValue=2, left=null, right=null], right=null], right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:19:46.743 [main] INFO jcg.zheng.demo.bst.DeleteService - found the deleting nodeBinaryNode [keyValue=2, left=null, right=null]
21:19:46.744 [main] INFO jcg.zheng.demo.bst.DeleteService - return null because the to-be-delete node 2 is a leaf node
21:19:46.745 [main] INFO jcg.zheng.demo.bst.DeleteServiceTest - End test_delete_left_leaf_node
Tests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.57 sec

Results :

Tests run: 5, Failures: 0, Errors: 0, Skipped: 0

4.6 TraverseServiceTest

In this step, I will create a TraverseServiceTest class which traverses nodes in four ways.

TraverseServiceTest.java

package jcg.zheng.demo.bst;

import org.junit.Test;

public class TraverseServiceTest extends TestBase {

	private TraverseService traversrv = new TraverseService();

	@Test
	public void testLevelOrder() {

		buildTree();

		logger.info("\nlevelOrder -Should print as 6 4 8 3 5 7 9 2 10");
		traversrv.levelOrder(bst.getRoot());

	}

	@Test
	public void testInOrder() {

		buildTree();

		logger.info("\ninOrder-Should print as 2 3 4 5 6 7 8 9 10 - ordered");
		traversrv.inOrder_sorted(bst.getRoot());

	}

	@Test
	public void testPreOrder() {

		buildTree();

		logger.info("\npreOrder-Should print as 6 4 3 2 5 8 7 9 10 - same order as the insert order");
		traversrv.preOrder(bst.getRoot());

	}

	@Test
	public void testPostOrder() {

		buildTree();

		logger.info("\npostOrder-Should print as 4 3 2 5 8 7 9 10 6");
		traversrv.postOrder(bst.getRoot());

	}

	private void buildTree() {
		bst.add(6);
		bst.add(4);
		bst.add(8);
		bst.add(3);
		bst.add(5);
		bst.add(7);
		bst.add(9);
		bst.add(2);
		bst.add(10);
	}

}

Execute the test and capture the output here.

Output

Running jcg.zheng.demo.bst.TraverseServiceTest
21:21:22.128 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - Start testPostOrder
21:21:22.135 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:21:22.138 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:21:22.201 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:21:22.202 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:8
21:21:22.203 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=8, left=null, right=null]
21:21:22.204 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:3
21:21:22.204 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=3, left=null, right=null]
21:21:22.205 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:5
21:21:22.206 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=BinaryNode [keyValue=3, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=5, left=null, right=null]
21:21:22.206 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:7
21:21:22.207 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=null, right=null] sets new left_node:BinaryNode [keyValue=7, left=null, right=null]
21:21:22.207 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:9
21:21:22.208 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=BinaryNode [keyValue=7, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=9, left=null, right=null]
21:21:22.208 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:21:22.209 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=3, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:21:22.209 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:21:22.209 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=9, left=null, right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:21:22.209 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest -
postOrder-Should print as 4 3 2 5 8 7 9 10 6
4 3 2 5 8 7 9 10 6 21:21:22.228 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - End testPostOrder
21:21:22.238 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - Start testPreOrder
21:21:22.240 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:21:22.241 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:21:22.242 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:21:22.242 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:8
21:21:22.242 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=8, left=null, right=null]
21:21:22.243 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:3
21:21:22.243 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=3, left=null, right=null]
21:21:22.243 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:5
21:21:22.244 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=BinaryNode [keyValue=3, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=5, left=null, right=null]
21:21:22.244 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:7
21:21:22.244 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=null, right=null] sets new left_node:BinaryNode [keyValue=7, left=null, right=null]
21:21:22.244 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:9
21:21:22.245 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=BinaryNode [keyValue=7, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=9, left=null, right=null]
21:21:22.246 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:21:22.247 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=3, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:21:22.248 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:21:22.249 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=9, left=null, right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:21:22.249 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest -
preOrder-Should print as 6 4 3 2 5 8 7 9 10 - same order as the insert order
6 4 3 2 5 8 7 9 10 21:21:22.256 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - End testPreOrder
21:21:22.257 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - Start testLevelOrder
21:21:22.258 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:21:22.258 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:21:22.259 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:21:22.259 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:8
21:21:22.260 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=8, left=null, right=null]
21:21:22.260 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:3
21:21:22.260 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=3, left=null, right=null]
21:21:22.261 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:5
21:21:22.262 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=BinaryNode [keyValue=3, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=5, left=null, right=null]
21:21:22.262 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:7
21:21:22.263 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=null, right=null] sets new left_node:BinaryNode [keyValue=7, left=null, right=null]
21:21:22.263 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:9
21:21:22.263 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=BinaryNode [keyValue=7, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=9, left=null, right=null]
21:21:22.264 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:21:22.265 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=3, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:21:22.266 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:21:22.266 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=9, left=null, right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:21:22.266 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest -
levelOrder -Should print as 6 4 8 3 5 7 9 2 10
6 4 8 3 5 7 9 2 10 21:21:22.274 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - End testLevelOrder
21:21:22.276 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - Start testInOrder
21:21:22.277 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:6
21:21:22.277 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:4
21:21:22.278 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=null, right=null] sets new left_node:BinaryNode [keyValue=4, left=null, right=null]
21:21:22.278 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:8
21:21:22.278 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=6, left=BinaryNode [keyValue=4, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=8, left=null, right=null]
21:21:22.279 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:3
21:21:22.279 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=null, right=null] sets new left_node:BinaryNode [keyValue=3, left=null, right=null]
21:21:22.282 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:5
21:21:22.282 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=4, left=BinaryNode [keyValue=3, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=5, left=null, right=null]
21:21:22.282 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:7
21:21:22.283 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=null, right=null] sets new left_node:BinaryNode [keyValue=7, left=null, right=null]
21:21:22.283 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:9
21:21:22.283 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=8, left=BinaryNode [keyValue=7, left=null, right=null], right=null] sets new right_node:BinaryNode [keyValue=9, left=null, right=null]
21:21:22.283 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:2
21:21:22.283 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=3, left=null, right=null] sets new left_node:BinaryNode [keyValue=2, left=null, right=null]
21:21:22.284 [main] INFO jcg.zheng.demo.bst.InsertService - Create a new leaf node with keyvalue:10
21:21:22.290 [main] INFO jcg.zheng.demo.bst.BinaryNode - Node:BinaryNode [keyValue=9, left=null, right=null] sets new right_node:BinaryNode [keyValue=10, left=null, right=null]
21:21:22.291 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest -
inOrder-Should print as 2 3 4 5 6 7 8 9 10 - ordered
2 3 4 5 6 7 8 9 10 21:21:22.293 [main] INFO jcg.zheng.demo.bst.TraverseServiceTest - End testInOrder
Tests run: 4, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.686 sec

Results :

Tests run: 4, Failures: 0, Errors: 0, Skipped: 0

4.7 JDKLibraryTest

As you seen here, it’s not hard to create your own implementation of BST. However, I’d like to point out that JDK provides a TreeSet class and Collections.binarySearch method. Both have a time complexity of O ( log n) when searching an element. In this step, I will create two test methods to demonstrate both.

JDKLibraryTest.java

package jcg.zheng.demo.bst;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

import org.junit.Test;

public class JDKLibraryTest {

    @Test
    public void TreeSet_is_same_as_BST_inOrder() {
        // TreeSet from JDK is basically implementation of a self-balancing binary search tree.
        // like Red-Black Tree, the add, remove, search take O(log n) time.
        TreeSet<Integer> ts = new TreeSet<>();

        ts.add(Integer.valueOf(6));
        ts.add(Integer.valueOf(4));
        ts.add(Integer.valueOf(8));
        ts.add(Integer.valueOf(3));
        ts.add(Integer.valueOf(5));
        ts.add(Integer.valueOf(7));
        ts.add(Integer.valueOf(9));
        ts.add(Integer.valueOf(2));
        ts.add(Integer.valueOf(10));
        System.out.println("should print out 2345678910");
        ts.forEach(bst -> System.out.print(bst)); // 2345678910

        boolean foundThree = ts.contains(Integer.valueOf(3));
        assertTrue(foundThree);
    }

    @Test
    public void collections_binarySearch() {
        List<Integer> testList = new ArrayList<>();
        for (int i = 10; i < 20; i++) {
            testList.add(Integer.valueOf(i));
        }

        int foundIndex = Collections.binarySearch(testList, 13);
        assertEquals(3, foundIndex);
    }

}

Execute the test and capture the output here.

Output

C:\MaryZheng\Workspaces\jcg-zheng-bst-demo>mvn test -Dtest=JDKLibraryTest
[INFO] Scanning for projects...
[INFO]
[INFO] ---------------< jcg-zheng-bst-demo:jcg-zheng-bst-demo >----------------
[INFO] Building jcg-zheng-bst-demo 0.0.1-SNAPSHOT
[INFO] --------------------------------[ jar ]---------------------------------
[INFO]
[INFO] --- maven-resources-plugin:2.6:resources (default-resources) @ jcg-zheng-bst-demo ---
[WARNING] Using platform encoding (Cp1252 actually) to copy filtered resources, i.e. build is platform dependent!
[INFO] skip non existing resourceDirectory C:\MaryZheng\Workspaces\jcg-zheng-bst-demo\src\main\resources
[INFO]
[INFO] --- maven-compiler-plugin:3.8.0:compile (default-compile) @ jcg-zheng-bst-demo ---
[INFO] Changes detected - recompiling the module!
[WARNING] File encoding has not been set, using platform encoding Cp1252, i.e. build is platform dependent!
[INFO] Compiling 8 source files to C:\MaryZheng\Workspaces\jcg-zheng-bst-demo\target\classes
[INFO]
[INFO] --- maven-resources-plugin:2.6:testResources (default-testResources) @ jcg-zheng-bst-demo ---
[WARNING] Using platform encoding (Cp1252 actually) to copy filtered resources, i.e. build is platform dependent!
[INFO] skip non existing resourceDirectory C:\MaryZheng\Workspaces\jcg-zheng-bst-demo\src\test\resources
[INFO]
[INFO] --- maven-compiler-plugin:3.8.0:testCompile (default-testCompile) @ jcg-zheng-bst-demo ---
[INFO] Nothing to compile - all classes are up to date
[INFO]
[INFO] --- maven-surefire-plugin:2.12.4:test (default-test) @ jcg-zheng-bst-demo ---
[INFO] Surefire report directory: C:\MaryZheng\Workspaces\jcg-zheng-bst-demo\target\surefire-reports

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running jcg.zheng.demo.bst.JDKLibraryTest
should print out 2345678910
2345678910Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.224 sec

Results :

Tests run: 2, Failures: 0, Errors: 0, Skipped: 0

[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  16.656 s
[INFO] Finished at: 2019-06-12T16:35:06-05:00
[INFO] ------------------------------------------------------------------------

C:\MaryZheng\Workspaces\jcg-zheng-bst-demo>

5. Binary Search Tree Java Example Summary

In this article, I created several Java classes to demonstrate how to construct a binary search tree and implement add, delete, and search operations. The time complexity of searching a node in a Binary Search Tree is O(n). However, the balanced Binary Search Tree has an O(log n) complexity.

Java also provides a TreeSet and TreeMap which implements Binary Search Tree for faster searching speed.

Binary Search Tree is used in the heap data structure for repeatedly removing the object with the highest (or lowest) priority. It’s also used in almost every 3D video game for determining what objects need to be rendered. It’s also used by high-bandwidth routers for storing router-tables. etc.

6. Download the Source Code

This tutorial consists of a Maven project which includes Java classes to define a Java Binary Search Tree class and provides add, delete & search operations.

Download
You can download the full source code of this example here: Binary Search Tree Java Example

Last updated on Mar. 04th, 2020

Photo of Mary Zheng Mary ZhengJune 21st, 2019Last Updated: May 15th, 2020
0 294 22 minutes read
Photo of Mary Zheng

Mary Zheng

Mary has graduated from Mechanical Engineering department at ShangHai JiaoTong University. She also holds a Master degree in Computer Science from Webster University. During her studies she has been involved with a large number of projects ranging from programming and software engineering. She works as a senior Software Engineer in the telecommunications sector where she acts as a leader and works with others to design, implement, and monitor the software solution.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button