Home » Core Java » Java Binary Search Tree Example

About 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.

Java Binary Search Tree 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.

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

  • Define a BST data structure
  • Traverse BST nodes
  • Add, delete, and search a node

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

3. Maven Project

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>
  </dependencies>
</project>

3.2 BinaryTreeNode

In this step, I will create a BinaryTreeNode class which defines a node with three data members:

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

BinaryTreeNode.java

package jcg.zheng.demo.bst;

/**
 * A binary tree is a data structure which each node can have at most 2 children.
 *
 */
public class BinaryTreeNode {

    private int keyValue;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

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

    public int getKeyValue() {
        return keyValue;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public void setKeyValue(int value) {
        this.keyValue = value;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }

}

3.3 BinarySearchTree

In this step, I will create a BinarySearchTree class which has two members:

  • root – the root node of the BST
  • crdService – an instance of BSTCRDService which provides add, delete, and search operations.

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 BSTCRDService crdService = new BSTCRDService();

    private BinaryTreeNode root;

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

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

    public int min() {
        return crdService.findMinValue(root);
    }

    public int max() {
        return crdService.findMaxValue(root);
    }

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

    public BinaryTreeNode getRoot() {
        return root;
    }

    public void setRoot(BinaryTreeNode root) {
        this.root = root;
    }

}

3.4 BSTCRDService

In this step, I will create a BSTCRDService class which provides add, delete, searchNode, findMinValue, and findMaxValue operations.

BSTCRDService.java

package jcg.zheng.demo.bst;

public class BSTCRDService {

    public BinaryTreeNode add(BinaryTreeNode current, int addingValue) {
        if (current == null) {
            return new BinaryTreeNode(addingValue);
        }

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

        return current;
    }

    public BinaryTreeNode delete(BinaryTreeNode current, int deletingValue) {
        if (current == null) {
            return null;
        }

        if (deletingValue == current.getKeyValue()) {
            if (current.getLeft() == null) {
                if (current.getRight() == null) {
                    // delete the leaf node
                    return null;
                } else {
                    // only right child
                    return current.getRight();
                }
            } else {
                if (current.getRight() == null) {
                    // only Left child
                    return current.getLeft();
                } else {
                    // has both children
                    int smallest = findMinValue(current.getRight());
                    current.setKeyValue(smallest);
                    current.setRight(delete(current.getRight(), smallest));

                    return current;
                }

            }
        } else if (deletingValue < current.getKeyValue()) {
            current.setLeft(delete(current.getLeft(), deletingValue));
            return current;
        } else {
            current.setRight(delete(current.getRight(), deletingValue));
            return current;
        }

    }

    public int findMinValue(BinaryTreeNode node) {
        return node.getLeft() == null ? node.getKeyValue() : findMinValue(node.getLeft());
    }

    public BinaryTreeNode searchNode(BinaryTreeNode current, int findingValue) {
        if (current == null) {
            return null;
        }

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

    }

    public Integer findMaxValue(BinaryTreeNode node) {
        return node.getRight() == null ? node.getKeyValue() : findMaxValue(node.getRight());
    }

}

3.5 TraverseBSTService

In this step, I will create a TraverseBSTService class which traverses BST nodes 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.
  • preOrder – traverses the nodes in BST based on the depth in root, left, right order.
  • postOrder – traverses the nodes in BST based on the depth in left, right, root order.

TraverseBSTService.java

package jcg.zheng.demo.bst;

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

public class TraverseBSTService {

    private static final String SPACE = " ";

    public void inOrder(BinaryTreeNode rootNode) {
        if (rootNode != null) {
            inOrder(rootNode.getLeft());
            print(rootNode);
            inOrder(rootNode.getRight());
        }

    }

    public void levelOrder(BinaryTreeNode rootNode) {

        if (rootNode == null)
            return;

        Queue fifoQueue = new LinkedList();

        fifoQueue.add(rootNode);

        while (!fifoQueue.isEmpty()) {
            rootNode = fifoQueue.poll();
            print(rootNode);

            if (rootNode.getLeft() != null) {
                fifoQueue.add(rootNode.getLeft());
            }

            if (rootNode.getRight() != null) {
                fifoQueue.add(rootNode.getRight());
            }
        }

    }

    public void postOrder(BinaryTreeNode rootNode) {
        if (rootNode != null) {
            preOrder(rootNode.getLeft());
            preOrder(rootNode.getRight());
            print(rootNode);
        }
    }

    public void preOrder(BinaryTreeNode rootNode) {
        if (rootNode != null) {
            print(rootNode);
            preOrder(rootNode.getLeft());
            preOrder(rootNode.getRight());
        }

    }

    private void print(BinaryTreeNode rootNode) {
        System.out.print(rootNode.getKeyValue() + SPACE);
    }

}

4. Test Classes

4.1 TestBase

In this step, I will create a TestBase class which contains the common test data and the setup method.

TestBase.java

package jcg.zheng.demo.bst;

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

import org.junit.Before;

public class TestBase {

    protected static final int MIN = 2;
    protected static final int MAX = 10;

    protected BinarySearchTree bst;
    protected TraverseBSTService tService = new TraverseBSTService();
    protected BSTCRDService crdService = new BSTCRDService();

    @Before
    public void setup() {
        bst = new BinarySearchTree();
        assertTrue(bst.isEmpty());
        bst.add(6);
        assertFalse(bst.isEmpty());
        bst.add(4);
        bst.add(8);
        bst.add(3);
        bst.add(5);
        bst.add(7);
        bst.add(9);
        bst.add(MIN);
        bst.add(MAX);

        System.out.println("\nOriginal Tree:");
        tService.preOrder(bst.getRoot());
    }

}

4.2 TraverseBSTServiceTest

In this step, I will create a TraverseBSTServiceTest class which tests four methods to traverse BST nodes.

TraverseBSTServiceTest.java

package jcg.zheng.demo.bst;

import org.junit.Test;

public class TraverseBSTServiceTest extends TestBase {

    @Test
    public void inOrder_left_root_right() {
        System.out.println("\nShould print as 2 3 4 5 6 7 8 9 10 - ordered");
        tService.inOrder(bst.getRoot());
    }

    @Test
    public void preOrder_root_left_right() {
        System.out.println("\nShould print as 6 4 3 2 5 8 7 9 10 - same as the insert");
        tService.preOrder(bst.getRoot());
    }

    @Test
    public void postOrder_left_right_root() {
        System.out.println("\nShould print as 4 3 2 5 8 7 9 10 6");
        tService.postOrder(bst.getRoot());
    }

    @Test
    public void levelOrder() {
        System.out.println("\nShould print as 6 4 8 3 5 7 9 2 10");
        tService.levelOrder(bst.getRoot());
    }

}

Execute the test and capture the output here.

Output

C:\MaryZheng\Workspaces\jcg-zheng-bst-demo>mvn test -Dtest=TraverseBSTServiceTest
[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] Changes detected - recompiling the module!
[WARNING] File encoding has not been set, using platform encoding Cp1252, i.e. build is platform dependent!
[INFO] Compiling 4 source files to C:\MaryZheng\Workspaces\jcg-zheng-bst-demo\target\test-classes
[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.TraverseBSTServiceTest

Original Tree:
6 4 3 2 5 8 7 9 10
Should print as 6 4 3 2 5 8 7 9 10 - same as the insert
6 4 3 2 5 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
Should print as 6 4 8 3 5 7 9 2 10
6 4 8 3 5 7 9 2 10
Original Tree:
6 4 3 2 5 8 7 9 10
Should print as 2 3 4 5 6 7 8 9 10 - ordered
2 3 4 5 6 7 8 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
Should print as 4 3 2 5 8 7 9 10 6
4 3 2 5 8 7 9 10 6 Tests run: 4, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.531 sec

Results :

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

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

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

4.3 BinarySearchTreeTest

In this step, I will create a BinarySearchTreeTest class which tests add, delete, searchNode, findMinValue, and findMaxValue methods.

BinarySearchTreeTest.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 BinarySearchTreeTest extends TestBase {

    @Test
    public void delete_max() {
        BinaryTreeNode existNode = crdService.searchNode(bst.getRoot(), MAX);
        assertNotNull(existNode);

        bst.delete(MAX);

        System.out.println("\nupdated list");
        tService.preOrder(bst.getRoot());

        BinaryTreeNode deletedNode = crdService.searchNode(bst.getRoot(), MAX);
        assertNull(deletedNode);

    }

    @Test
    public void delete_min() {
        BinaryTreeNode existNode = crdService.searchNode(bst.getRoot(), MIN);
        assertNotNull(existNode);

        bst.delete(MIN);

        System.out.println("\nupdated list");
        tService.preOrder(bst.getRoot());

        BinaryTreeNode deletedNode = crdService.searchNode(bst.getRoot(), MIN);
        assertNull(deletedNode);

    }

    @Test
    public void delete_only_left_child() {
        BinaryTreeNode existNode = crdService.searchNode(bst.getRoot(), 3);
        assertNotNull(existNode);

        bst.delete(3);

        System.out.println("\nupdated list");
        tService.preOrder(bst.getRoot());

        BinaryTreeNode deletedNode = crdService.searchNode(bst.getRoot(), 3);
        assertNull(deletedNode);

    }

    @Test
    public void delete_only_right_child() {
        BinaryTreeNode existNode = crdService.searchNode(bst.getRoot(), 9);
        assertNotNull(existNode);

        bst.delete(9);
        System.out.println("\nupdated list");
        tService.preOrder(bst.getRoot());

        BinaryTreeNode deletedNode = crdService.searchNode(bst.getRoot(), 9);
        assertNull(deletedNode);

    }

    @Test
    public void delete_subtreeNode() {
        BinaryTreeNode existNode = crdService.searchNode(bst.getRoot(), 4);
        assertNotNull(existNode);

        bst.delete(4);
        System.out.println("\nupdated list");
        tService.preOrder(bst.getRoot());

        BinaryTreeNode deletedNode = crdService.searchNode(bst.getRoot(), 4);
        assertNull(deletedNode);

    }

    @Test
    public void findMin() {
        int minValue = bst.min();
        assertEquals(2, minValue);
    }

    @Test
    public void findMax() {
        int minValue = bst.max();
        assertEquals(10, minValue);
    }

    @Test
    public void searchNode_found() {
        BinaryTreeNode existNode = crdService.searchNode(bst.getRoot(), 4);
        assertNotNull(existNode);
        assertEquals(4, existNode.getKeyValue());
        assertNotNull(existNode.getLeft());

        assertNotNull(existNode.getRight());
    }

    @Test
    public void searchNode_not_found() {
        BinaryTreeNode notexistNode = crdService.searchNode(bst.getRoot(), 11);
        assertNull(notexistNode);
    }

}

Execute the test and capture the output here.

Output

C:\MaryZheng\Workspaces\jcg-zheng-bst-demo>mvn test -Dtest=BinarySearchTreeTest
[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] Changes detected - recompiling the module!
[WARNING] File encoding has not been set, using platform encoding Cp1252, i.e. build is platform dependent!
[INFO] Compiling 4 source files to C:\MaryZheng\Workspaces\jcg-zheng-bst-demo\target\test-classes
[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.BinarySearchTreeTest

Original Tree:
6 4 3 2 5 8 7 9 10
updated list
6 4 3 2 5 8 7 10
Original Tree:
6 4 3 2 5 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
updated list
6 4 2 5 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
updated list
6 5 3 2 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
Original Tree:
6 4 3 2 5 8 7 9 10
updated list
6 4 3 2 5 8 7 9
Original Tree:
6 4 3 2 5 8 7 9 10
updated list
6 4 3 5 8 7 9 10 Tests run: 9, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 1.47 sec

Results :

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

[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  27.571 s
[INFO] Finished at: 2019-06-12T16:13:32-05:00
[INFO] ------------------------------------------------------------------------

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

4.4 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. Java Binary Search Tree – Summary

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

Java also provides a TreeSet and TreeMap which implements BST for faster searching speed.

BST 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: Java Binary Search Tree Example
(+4 rating, 4 votes)
Start the discussion Views Tweet it!

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

Leave a Reply

avatar
  Subscribe  
Notify of