Binary Search Tree (BST)

A Binary Search Tree is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.

1 Insertion

Starting from the root, we compare the value to be inserted with the current node's value. If it's smaller, we move to the left child; if larger, to the right. We repeat this until we find an empty spot.

2 Searching

Similar to insertion, we traverse the tree based on comparisons. If we find a match, we return the node. If we reach a null child, the value doesn't exist.

3 Deletion

Three cases:
1. Leaf node: Simple removal.
2. One child: Replace node with its child.
3. Two children: Find inorder successor (smallest in right subtree), replace node's value with successor, and delete successor.

4 Traversals


Inorder: Left, Root, Right (Results in sorted order).
Preorder: Root, Left, Right.
Postorder: Left, Right, Root.

Complexity Analysis

Average Case

O(log n)

For Search, Insert, and Delete.

Worst Case

O(n)

Occurs when the tree becomes skewed (like a linked list).

Visualization Logic

/**
 * We use an async state recording system.
 * Every structural change or comparison is recorded
 * as a 'Step' containing a clone of the tree.
 */
function recordStep(description, highlights) {
    steps.push({
        tree: cloneTree(root),
        description: description,
        highlights: highlights
    });
}