In this article, we will learn about Binary Search Tree data structure and how to implement it in Java

Tree Data Structure

Tree is a non-linear data structure consisting of a collection of nodes which are organized in hierarchy way

Binary Tree Data Structure

Binary Tree is a tree data structure in which each node has at most 2 children, left child and right child

Binary Search Tree Data Structure

Binary Search Tree, aka ordered/sorted binary tree, is a binary tree in which all parent nodes's value are greater than theirs left child's value and less than theirs right child's value

Basic operations

  • Traversal: visits each node in a tree exactly once

  • Insert: adds a new node into a tree

  • Delete: removes a node from a tree


You can implement a binary search tree with either a linked list, static array (capacity restricted) or a dynamic array

The following is an implementation example with Linked List

public class BSTByLinkedList {  
    public Node root;

    private Node insert(Node node, int data) {
        if (node == null) {
            return new Node(data);

        if (data < {
            node.left = insert(node.left, data);
        } else if (data >  {
            node.right = insert(node.right, data);

        return node;

    public void insert(int data) {
        this.root = insert(this.root, data);

    public void inTraversal(Node node) {
        if (node == null) return;


    public static void main(String[] args) {
        BSTByLinkedList tree = new BSTByLinkedList();


    public static class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
   = data;

        public String toString() {
            return String.format("data: %d, left: %d, right: %d", data, (left !=null ? : null), (right != null? : null));