Introduction

A Binary Search Tree (BST) is a special type of binary tree that maintains a sorted order of elements, allowing for efficient search, insertion, and deletion operations. Similar to a regular binary tree, a Binary Search Tree (BST) can be traversed using preorder, inorder, postorder, or level-order methods. However, an important point to note is that the inorder traversal of a BST always results in elements being visited in ascending order. Because of this property, inorder traversal is the most commonly used method for traversing a BST.

The goal of this articles are followings.

• ✅ Grasp the fundamental properties of binary trees,
• ✅ Perform basic operations on a binary search tree,
• ✅ Understand the concept of a height-balanced BST.

Properties of the Binary Search Tree

Each node of BST follows these properties:

1. Left Subtree Property:

The left subtree of a node contains only nodes with values less than the node's value.

2. Right Subtree Property:

The right subtree of a node contains only nodes with values greater than the node's value.

3. No Duplicates:

Typically, BSTs do not allow duplicate values.

4. Recursive Structure:

Each left and right subtree must also be a BST.

Example of a BST:

The left subtree of 8 includes all nodes that are less than 8.
The right subtree of 3 includes all nodes that are greater than 3.

Time complexity of BST

The efficiency of operations in a BST depends on the height of the tree.

Searching in a BST

The search operation in a BST follows these steps:

1. Start at the root node.
2. If the key matches the root, return the node.
3. If the key is smaller, search in the left subtree.
4. If the key is greater, search in the right subtree.
5. Repeat this process recursively until the key is found or the subtree is empty.

Best and Average Case O(log n)

If the BST is balanced, each comparison halves the number of remaining nodes to check. Thus, search takes O(log n) time.

Worst Case O(n)

If the BST is skewed (all nodes form a linked list), every search must traverse all n nodes. In this case, the time complexity degrades to O(n).

Searching Implementation in Java

1. Recursive Approach

2. Iterative Approach

Insertion in a BST

Insertion follows a process similar to searching:

1. Start at the root.
2. Compare the key with the current node.
3. Move left if the key is smaller, move right if it's larger.
4. When an empty spot is found, insert the new node.

Best & Average Case O(log n)

When the tree is balanced.

Worst Case O(n)

When inserting sorted data into an unbalanced BST.

Insertion Implementation in Java

1. Recursive Approach

2. Iterative Approach

Deletion in a BST

Deletion is more complicated than those two operations above.

Deleting a node has three cases:

i) Node has no children -> Simply remove it.
ii) Node has one child -> Replace it with its child.
iii) Node has two children -> Replace the node with its in-order successor (leftmost node in right subtree) or predecessor (rightmost node in the left subtree) node and delete that node.

Example: Inorder Successor vs Predecessor in BST

Inorder Traversal:

1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14

Inorder Successor is left node of current node while Inorder Predecessor is right node of current node.

Best & Average Case O(log n)

If the tree is balanced, we find and delete the node in logarithmic time.

Worst Case O(n)

If the tree is skewed, deletion takes linear time.

Deletion Implementation in Java

1. Recursive Approach