Binary Search Tree: Implementation and Operations

1. What is a Binary Search Tree?

A Binary Search Tree is a binary tree with a special property that governs the placement of all its nodes:

For any given node N:

1. All values in N's left subtree are less than N's value.
2. All values in N's right subtree are greater than N's value.
3. Both the left and right subtrees must also be binary search trees.

This ordering principle is the key to the BST's efficiency.

To start, let's watch a short video that provides a high-level overview of this concept.

2. Implementation: The Basic Structure

Given your background in Java and Object-Oriented Programming, setting up the classes will be straightforward. We need two classes:

1. Node: Represents a single node in the tree. It holds some data (we'll use an integer key) and references to its left and right children.
2. BinarySearchTree: Represents the entire tree. It typically only needs one field: a reference to the root node.

Here's the basic structure from the article:

// Represents a single node in the BST
class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

// Represents the entire BST
class BinarySearchTree {
    // The root of the BST
    Node root;

    // Constructor
    public BinarySearchTree() {
        root = null;
    }

    // We will add our methods here...
}

3. Insertion and Search Operations

Insertion and searching in a BST both leverage the core ordering property. The logic for deciding whether to go left or right is the same for both.

• To search for a value: Start at the root. If the target value is equal to the current node's key, you've found it. If it's smaller, move to the left child. If it's larger, move to the right child. If you reach a null reference, the value is not in the tree.
• To insert a value: Follow the same path as if you were searching for the value. When you reach a null reference, that's the spot where the new node should be attached.

Let's see how this is implemented. Recursion provides a very elegant solution for these tree operations.

While recursion is elegant, it's also important to know the iterative approach, which you may be asked for in an interview. Iterative solutions use a loop and a pointer that traverses the tree, avoiding the overhead of the call stack.

Here is an example of an iterative insertion method from the DigitalOcean article Binary Search Tree (BST) - Search Insert and Remove.

public Node insertIteratively(Node root, int value) {
    Node newNode = new Node(value);
    if (root == null) {
        return newNode;
    }

    Node current = root;
    Node parent = null;

    while (current != null) {
        parent = current;
        if (value < current.key) {
            current = current.left;
        } else if (value > current.key) {
            current = current.right;
        } else {
            // Value already exists, do nothing (or handle as needed)
            return root;
        }
    }

    // Attach the new node to the correct parent
    if (value < parent.key) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    return root;
}

4. Deletion Operation

Deletion is the most complex operation because we must ensure the BST property is maintained after the node is removed. We handle deletion by considering three distinct cases.

To see the complete logic for all three cases explained and implemented, the following resource is excellent.

Let's break down the logic from the video.

Case 1: The node to be deleted is a leaf (no children).

This is the simplest case. We can simply remove the node by setting its parent's reference to it to null.

Case 2: The node to be deleted has one child.

We can remove the node by "promoting" its single child to take its place. The parent of the node to be deleted will now point directly to its grandchild.

Case 3: The node to be deleted has two children.

This is the most involved case. We cannot simply remove the node, as that would leave two orphaned subtrees. Instead, we find a replacement node that can take its place without violating the BST property. We have two choices for this replacement:

1. The inorder successor: The smallest node in the node's right subtree.
2. The inorder predecessor: The largest node in the node's left subtree.

The standard approach is to use the inorder successor. The algorithm is:

1. Find the inorder successor (the minimum value in the right subtree).
2. Copy the value of the successor into the node you intended to delete.
3. Now, the original problem is transformed: we must recursively delete the successor from the right subtree.

This is a clever trick because the inorder successor is guaranteed to have at most one child (its right child), so its deletion will always fall into Case 1 or Case 2, which are simpler to handle.

5. Complexity Analysis

The efficiency of BST operations depends entirely on the tree's height, $h$.

• Best/Average Case (Balanced Tree): When the tree is reasonably balanced, its height is approximately $\log n$, where $n$ is the number of nodes. In this scenario, search, insert, and delete all have a time complexity of $O(\log n)$.
• Worst Case (Skewed Tree): If you insert elements in sorted order (e.g., 1, 2, 3, 4, 5), the tree becomes a long chain, essentially a linked list. The height becomes $n$. In this case, search, insert, and delete all degenerate to a time complexity of $O(n)$.

This worst-case performance is why self-balancing BSTs, such as AVL trees and Red-Black trees, were invented. We will cover them later in the course.

Conclusion

Great job completing this foundational lesson! You have now implemented the three core operations that define a Binary Search Tree. This is a must-know data structure for any aspiring software engineer, as it forms the basis for many interview questions and more advanced data structures.

Key Takeaways:

• A BST maintains the property: left child < parent < right child.
• This property allows search and insert operations to be performed efficiently by traversing a single path from the root.
• delete is the most complex operation, requiring three separate cases for handling nodes with zero, one, or two children.
• The two-child deletion case is elegantly solved by replacing the node's value with its inorder successor and then recursively deleting that successor.
• The performance of a BST is $O(\log n)$ on average but degrades to $O(n)$ for unbalanced, skewed trees.

Preview of the Next Lesson:
Now that you know how to build a BST, a classic follow-up problem is to verify if a given tree adheres to the rules. In the next lesson, we will tackle exactly that: Validate if a given binary tree is a BST. This problem will test your understanding of the BST property in a more subtle way.