Binary Search Tree Operations

1. The Binary Search Tree Property

A Binary Search Tree is a binary tree with a strict ordering constraint. This constraint, known as the BST property, is what gives the tree its power:

For any given node N in the tree:

• All values in N's left subtree are less than N's value.
• All values in N's right subtree are greater than N's value.
• This property must hold true for all nodes in the tree, making both the left and right subtrees binary search trees themselves.

This recursive definition ensures that if you perform an inorder traversal on a BST, you will visit the nodes in ascending (sorted) order. This is a fundamental property and a common check in GATE questions.

A valid Binary Search Tree. Notice that for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. An inorder traversal (Left-Root-Right) would yield: 3, 4, 6, 7, 8, 10, 13, 14.

A quick note on duplicate values: the standard BST definition doesn't allow them. In practice, if duplicates are needed, a consistent rule is applied, such as always placing them in the left or right subtree (e.g., left subtree values are less than or equal to the node's value). For GATE, if a question involves duplicates, the rule will be explicitly stated.

2. Search and Insertion Operations

The BST property makes searching for an element highly efficient, analogous to a binary search in a sorted array. The algorithm is intuitive:

1. Start at the root.
2. If the search key matches the current node's value, you've found it.
3. If the search key is less than the current node's value, move to the left child.
4. If the search key is greater than the current node's value, move to the right child.
5. Repeat until the key is found or you hit a NULL pointer (meaning the key is not in the tree).

Insertion ingeniously uses the same logic. To insert a new value, you perform a search for it. The search will eventually fail by reaching a NULL pointer. This NULL location is precisely where the new node should be attached as a leaf to maintain the BST property.

The following video provides an excellent walkthrough of BST construction by repeated insertions, a very common format for GATE questions.

3. Deletion: The Three Cases

Deleting a node from a BST is more complex than insertion because removing a node might disconnect the tree. The deletion algorithm is handled by considering three cases based on the number of children the node to be deleted has.

Case 2: Node has two children. This is the most involved case and the one most likely to be tested. We cannot simply remove the node, as it has two subtrees that need to remain connected. The solution is clever:

1. Find a replacement node from within the tree that can take the deleted node's place without violating the BST property.
2. The two best candidates for this are the node's inorder successor (the smallest value in its right subtree) or its inorder predecessor (the largest value in its left subtree).
3. Copy the value of the successor (or predecessor) into the node you want to delete.
4. Now, the tree has a duplicate value. The final step is to delete the original successor (or predecessor) node from its position.

The key insight is that the inorder successor/predecessor will have at most one child, so deleting it becomes a simple Case 0 or Case 1 problem!

Before we see this in action, let's take a dedicated look at how to find an inorder successor.

4. Finding the Inorder Successor/Predecessor

While finding the successor is part of the deletion algorithm, it is also a standalone problem often asked in GATE. You need to be able to find the successor of any given node efficiently.

There are two scenarios for finding the inorder successor of a node N:

• Scenario A: Node N has a right subtree. The successor is the smallest element in this right subtree. To find it, you simply go to the right child once, and then as far left as possible.
• Scenario B: Node N does not have a right subtree. The successor is the lowest ancestor of N for which N is in its left subtree. You have to travel up from N to find this ancestor.

The following video from mycodeschool is a classic and provides one of the clearest explanations of this logic.

Finding the inorder predecessor follows a symmetric logic:

• If the node has a left subtree, the predecessor is the largest element in that subtree (go left once, then as far right as possible).
• If the node has no left subtree, the predecessor is the lowest ancestor for which the node is in its right subtree.

Now, equipped with this knowledge, let's tackle the two-child deletion case.

5. Complexity Analysis

The performance of all BST operations—search, insert, and delete—depends on the height of the tree (h). In each step of these operations, we move down one level, so the time complexity is $O(h)$.

• Average/Best Case: For a reasonably balanced tree with n nodes, the height h is approximately ${\log }_{2}n$. This gives us the highly efficient $O(\log n)$ time complexity.
• Worst Case: If the tree is highly unbalanced (e.g., you insert keys in sorted order), it degenerates into a skewed tree that resembles a linked list. In this case, the height h becomes n, and the time complexity degrades to a linear $O(n)$.

Understanding this trade-off is critical. The video you've been watching concludes with a clear analysis of this.

Conclusion

In this lesson, you've learned the mechanics of the Binary Search Tree, a cornerstone data structure. You now understand the power and the limitations that stem from its core ordering property.

Key Takeaways:

• BST Property: Left < Root < Right. This enables an inorder traversal to produce a sorted sequence.
• Search & Insertion: Both operations follow a simple path from the root down, taking $O(h)$ time. Insertion is like a failed search that adds a new leaf.
• Deletion: This is the most complex operation, with three cases:
  • 0 Children (Leaf): Just remove it.
  • 1 Child: Bypass the node.
  • 2 Children: Replace the node with its inorder successor (or predecessor), then delete the successor/predecessor (which is now a Case 0 or Case 1 problem).
• Inorder Successor/Predecessor: You must know how to find this efficiently, considering the two cases (with or without a right/left subtree).
• Complexity: All core operations are $O(h)$. This is $O(\log n)$ for balanced trees but degrades to $O(n)$ for skewed trees.

This last point about the worst-case performance is not just a theoretical curiosity; it's a major practical problem. What if we could ensure the tree always stays balanced, no matter what we insert or delete? That is the question that leads us to our next lesson on AVL Trees, a type of self-balancing binary search tree that guarantees $O(\log n)$ performance.