Fundamentals of Binary Search Tree (Java)

Binary Search Trees (BSTs) are essential data structures in computer science that enable efficient data storage, retrieval, and manipulation. They are structured to ensure efficient search operations, making them a cornerstone of many algorithms and applications.

In this blog, we will walk through a Java implementation of a Binary Search Tree and explain its components, functionality, and usage.

What is a Binary Search Tree?

A Binary Search Tree is a type of binary tree where:

1. Each node contains a key.

2. Keys in the left subtree are less than the node's key.

3. Keys in the right subtree are greater than the node's key.

4. Both the left and right subtrees are also BSTs.

This hierarchical structure allows operations like search, insertion, and deletion to run efficiently.

Code Walkthrough

Let’s analyze the implementation step by step.

1. Node Class

    class Node {
        int data;
        Node leftChild;
        Node rightChild;
        public Node(int data){
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
        public int getData(){
            return this.data;
        }
    }
   

   Explanation:

   • Attributes:

     • data: Stores the value of the node.

     • leftChild and rightChild: References to the left and right child nodes, respectively.

   • Constructor:

     • Initializes the node with the given data and sets child references to null.

   • Accessor Method:

     • getData() provides access to the data attribute.

2. BinarySearchTree Class

    class BinarySearchTree {
        Node rootNode;
        public BinarySearchTree(){
            this.rootNode = null;
        }
    }
   

   Explanation:

   • Attribute:

     • rootNode: The entry point of the BST.

   • Constructor:

     • Initializes an empty BST with rootNode set to null.

3. Insertion Method

    Node insert(Node root, int data) {
        if (root == null) { 
            root = new Node(data); 
            return root; 
        }
        if (data < root.getData()) 
            root.leftChild = insert(root.leftChild, data); 
        else if (data > root.getData()) 
            root.rightChild = insert(root.rightChild, data);
        return root; 
    }
   

   Key Points:

   • Base Case:

     • If the current root is null, create a new node with the given data and return it.

   • Recursive Insertion:

     • If data is smaller than the root’s data, insert it into the left subtree.

     • If data is greater, insert it into the right subtree.

Efficiency:

• Time Complexity: O(log⁡ n) in a balanced tree and O(n) in the worst-case (skewed tree).

4. In-Order Traversal

    void inorder(Node root) { 
        if (root != null) { 
            inorder(root.leftChild); 
            System.out.println(root.getData()); 
            inorder(root.rightChild); 
        } 
    }
   

   Explanation:

   • Traversal Order: Left → Root → Right

   • Functionality:

     • Recursively traverses the left subtree.

     • Prints data of the current node.

     • Recursively traverses the right subtree.

   • Result: Produces the elements in sorted order.

5. Solution Class (Main Functionality)

    class Solution {
        public static void main(String[] args){
            BinarySearchTree tree = new BinarySearchTree();
   
            tree.rootNode = tree.insert(tree.rootNode, 50);
            tree.rootNode = tree.insert(tree.rootNode, 30);
            tree.rootNode = tree.insert(tree.rootNode, 20);
            tree.rootNode = tree.insert(tree.rootNode, 40);
            tree.rootNode = tree.insert(tree.rootNode, 70);
            tree.rootNode = tree.insert(tree.rootNode, 60);
            tree.rootNode = tree.insert(tree.rootNode, 80);
            tree.inorder(tree.rootNode);
        }
    }
   

   Steps:

   1. Create a BinarySearchTree Instance:

      • Initialize an empty BST.

   2. Insert Elements:

      • Add elements (50, 30, 20, 40, 70, 60, 80) to the BST.

   3. Perform In-Order Traversal:

      • Print the elements in sorted order.

Output

The output of the in-order traversal is:

20
30
40
50
60
70
80

This confirms the correctness of the BST implementation.

Tree Visualization

Here’s how the BST looks after inserting the elements:

         50
       /    \
     30      70
    /  \    /  \
  20   40  60   80

Advantages of Binary Search Trees

1. Efficient Operations:

   • Average-case time complexity for insertion, deletion, and search is O(log⁡n)O(\log n)O(logn).

2. Sorted Data:

   • In-order traversal produces a sorted sequence.

3. Dynamic Structure:

   • BSTs adapt dynamically to changes in data.

Challenges

1. Skewed Trees:

   • If data is inserted in a sorted manner, the tree becomes unbalanced, degrading performance to O(n)O(n)O(n).

2. Balancing:

   • Self-balancing trees like AVL or Red-Black Trees address this issue.

Conclusion

This implementation provides a foundational understanding of Binary Search Trees in Java. It highlights their efficiency in storing and retrieving data and their simplicity in implementation.

Feel free to extend this code to include additional functionalities like deletion or balancing mechanisms. Happy coding!

References

1. Find the code for the above explanation here.