Home Data Structures and Algorithms with Java Binary Search Trees in Java

Lesson 14 of 48

In Progress

← Previous Next→

Binary Search Trees in Java

Yasin Cakal

Binary search trees (BSTs) are a type of data structure used to store data in a way that allows for efficient search, insertion, and deletion. They are commonly used in software development, and are an integral part of the “data structures and algorithms” courses. In this article, we will discuss what binary search trees are, how they work, their time and space complexities, and how to implement them in Java. We will also include 5 coding exercises with solutions for you to test your understanding of the material.

What are Binary Search Trees?

A binary search tree is a type of data structure used to store data in a hierarchical structure. Each node in the tree is referred to as a “parent” node, and each node can have up to two “child” nodes, one on the left side and one on the right side. The data in each node is sorted in such a way that data in the left child node is always less than the data in the parent node, and the data in the right child node is always greater than the data in the parent node. This allows us to quickly find a specific piece of data by comparing it to the data in the parent node. If the data is less than the parent node’s data, we can continue searching in the left child node; if it is greater than the parent node’s data, we can continue searching in the right child node. This process is repeated until the data is found or until there are no more child nodes to search.

In the case of a binary search tree, the data is typically stored in the form of a tree, with the root node at the top and the leaves (nodes without children) at the bottom. Each node in the tree contains a piece of data, and the ordering of the data is determined by the structure of the tree. This structure allows us to quickly search for a specific piece of data by comparing it to the data in the parent node.

How Binary Search Trees Work

Binary search trees are designed to store data in a way that allows for efficient search, insertion, and deletion. To do this, the tree must be organized in such a way that it can quickly access the data it needs. To begin, the tree must be balanced, meaning that the left and right subtrees of each node must contain the same number of nodes. This ensures that the tree is of optimal size, and that the time required to search for a particular piece of data is minimized.

Once the tree is balanced, the next step is to determine the order in which the data should be stored. This is done by comparing the data in each node to the data in its parent node. If the data is less than the parent node’s data, it is stored in the left subtree; if it is greater than the parent node’s data, it is stored in the right subtree. This process is repeated until the data is inserted into the correct position in the tree.

Time Complexity

The time complexity of a binary search tree is determined by the number of nodes in the tree and the structure of the tree. The time required to search for a particular piece of data is proportional to the height of the tree. In the best case, the tree is perfectly balanced, and the time required to search is O(log n), where n is the number of nodes in the tree. In the worst case, the tree is unbalanced, and the time required to search is O(n).

Insertion and deletion in a binary search tree is also O(log n) in the best case, and O(n) in the worst case. This is because the insertion and deletion algorithms must traverse the tree in order to find the correct position for the new data or the data to be deleted.

Space Complexity

The space complexity of a binary search tree is determined by the size of the data and the structure of the tree. In the worst case, the tree is unbalanced, and the space required to store the data is O(n2).

Implementing Binary Search Trees in Java

Now that we have discussed what binary search trees are and how they work, let’s take a look at how to implement them in Java. To begin, we will create a Node class to represent each node in the tree. The Node class will contain a piece of data, a pointer to the left child node, and a pointer to the right child node.

public class Node { 
    int data; 
    Node left; 
    Node right; 
 
    public Node(int data) { 
        this.data = data; 
        left = null; 
        right = null; 
    } 
}

Next, we will create a BinarySearchTree class to represent the tree. This class will contain a pointer to the root node, as well as methods for searching, inserting, and deleting data from the tree.

public class BinarySearchTree { 
    Node root; 
 
    public BinarySearchTree() { 
        root = null; 
    } 
 
    public void insert(int data) { 
        // code to insert data 
    } 
 
    public void search(int data) { 
        // code to search for data 
    } 
 
    public void delete(int data) { 
        // code to delete data 
    } 
}

Conclusion

In this article, we have discussed binary search trees, how they work, their time and space complexities, and how to implement them in Java. Binary search trees are an efficient way to store data in a hierarchical structure, and they are commonly used in software development. With a properly balanced tree, the time required to search for a particular piece of data is O(log n), and the time required to insert and delete data is also O(log n). The space complexity of a binary search tree is O(n2) in the worst case.

Exercises

Write a Java program to create a binary search tree with the following values: 10, 5, 15, 2, 8, 12, 20.

public class BinarySearchTree { 
    Node root; 
 
    public BinarySearchTree() { 
        root = null; 
    } 
 
    public void insert(int data) { 
        Node newNode = new Node(data); 
        if (root == null) { 
            root = newNode; 
        } else { 
            Node current = root; 
            Node parent; 
            while (true) { 
                parent = current; 
                if (data < current.data) { 
                    current = current.left; 
                    if (current == null) { 
                        parent.left = newNode; 
                        return; 
                    } 
                } else { 
                    current = current.right; 
                    if (current == null) { 
                        parent.right = newNode; 
                        return; 
                    } 
                } 
            } 
        } 
    } 
} 
// Create a BinarySearchTree object 
BinarySearchTree bst = new BinarySearchTree(); 

// Insert the following values into the tree 
bst.insert(10); 
bst.insert(5); 
bst.insert(15); 
bst.insert(2); 
bst.insert(8); 
bst.insert(12); 
bst.insert(20);

Write a Java program to search for a number in a binary search tree.

public class BinarySearchTree { 
    Node root; 
 
    public BinarySearchTree() { 
        root = null; 
    } 
 
    public void search(int data) { 
        Node current = root; 
        while (current != null) { 
            if (data == current.data) { 
                System.out.println("Number found!"); 
                return; 
            } else if (data < current.data) { 
                current = current.left; 
            } else { 
                current = current.right; 
            } 
        } 
        System.out.println("Number not found!"); 
    } 
} 

// Create a BinarySearchTree object 
BinarySearchTree bst = new BinarySearchTree(); 

// Insert some numbers into the tree 
bst.insert(10); 
bst.insert(5); 
bst.insert(15); 
bst.insert(2); 
bst.insert(8); 
bst.insert(12); 
bst.insert(20); 

// Search for a number 
bst.search(12); // Number found! 
bst.search(7); // Number not found!

Write a Java program to delete a number from a binary search tree.

public class BinarySearchTree { 
    Node root; 
 
    public BinarySearchTree() { 
        root = null; 
    } 
 
    public void delete(int data) { 
        root = deleteRecursive(root, data); 
    } 
 
    private Node deleteRecursive(Node current, int data) { 
        if (current == null) { 
            return null; 
        } 
 
        if (data == current.data) { 
            // Node to delete found 
            if (current.left == null && current.right == null) { 
                return null; 
            } 
            if (current.right == null) { 
                return current.left; 
            } 
            if (current.left == null) { 
                return current.right; 
            } 
            int smallestValue = findSmallestValue(current.right); 
            current.data = smallestValue; 
            current.right = deleteRecursive(current.right, smallestValue); 
            return current; 
        } 
        if (data < current.data) { 
            current.left = deleteRecursive(current.left, data); 
            return current; 
        } 
        current.right = deleteRecursive(current.right, data); 
        return current; 
    } 
 
    private int findSmallestValue(Node root) { 
        return root.left == null ? root.data : findSmallestValue(root.left); 
    } 
} 

// Create a BinarySearchTree object 
BinarySearchTree bst = new BinarySearchTree(); 

// Insert some numbers into the tree 
bst.insert(10); 
bst.insert(5); 
bst.insert(15); 
bst.insert(2); 
bst.insert(8); 
bst.insert(12); 
bst.insert(20); 

// Delete a number from the tree 
bst.delete(15);

Write a Java program to traverse a binary search tree in pre-order.

public class BinarySearchTree { 
    Node root; 
 
    public BinarySearchTree() { 
        root = null; 
    } 
 
    public void preOrderTraversal() { 
        preOrderTraversalRecursive(root); 
    } 
 
    private void preOrderTraversalRecursive(Node current) { 
        if (current != null) { 
            System.out.println(current.data); 
            preOrderTraversalRecursive(current.left); 
            preOrderTraversalRecursive(current.right); 
        } 
    } 
} 

// Create a BinarySearchTree object 
BinarySearchTree bst = new BinarySearchTree(); 

// Insert some numbers into the tree 
bst.insert(10); 
bst.insert(5); 
bst.insert(15); 
bst.insert(2); 
bst.insert(8); 
bst.insert(12); 
bst.insert(20); 

// Traverse the tree in pre-order 
bst.preOrderTraversal(); // 10, 5, 2, 8, 15, 12, 20

Write a Java program to check if a given binary search tree is balanced.

public class BinarySearchTree { 
    Node root; 
 
    public BinarySearchTree() { 
        root = null; 
    } 
 
    public boolean isBalanced() { 
        return isBalancedRecursive(root); 
    } 
 
    private boolean isBalancedRecursive(Node current) { 
        if (current == null) { 
            return true; 
        } 
 
        int leftHeight = getHeight(current.left); 
        int rightHeight = getHeight(current.right); 
 
        return Math.abs(leftHeight - rightHeight) <= 1 && 
               isBalancedRecursive(current.left) && 
               isBalancedRecursive(current.right); 
    } 
 
    private int getHeight(Node node) { 
        if (node == null) { 
            return 0; 
        } 
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1; 
    } 
} 

// Create a BinarySearchTree object 
BinarySearchTree bst = new BinarySearchTree(); 

// Insert some numbers into the tree 
bst.insert(10); 
bst.insert(5); 
bst.insert(15); 
bst.insert(2); 
bst.insert(8); 
bst.insert(12); 
bst.insert(20); 

// Check if the tree is balanced 
bst.isBalanced(); // true

Data Structures and Algorithms with Java

Participants 433