Lesson 9 · Non-linear structures

Binary Search Trees

Binary Search Trees impose an ordering constraint on nodes, ensuring that left children are smaller and right children are larger than their parents.

The BST Invariant

The defining characteristic of a Binary Search Tree (BST) is its invariant: for any given node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater. This global property enables fast binary search.

Logarithmic Search

When searching for a value in a BST, we start at the root. If the target is smaller, we only search the left subtree. If larger, we search the right. This halves the search space at each step, yielding an average time complexity of O(log N) for insertions, deletions, and lookups.

Key reference

Terms, operations, and practical uses

BST Fundamentals

BST InvariantThe rule that for any node, all values in the left subtree are smaller, and all values in the right subtree are larger.
Search OperationsFinding a value by comparing it to the current node and moving left if smaller, or right if larger, in O(log N) average time.
Inorder PredecessorThe node with the largest value in the left subtree; it is the value immediately preceding the current node in sorted order.

Tree Modification

InsertionTraversing down the tree until a null leaf pointer is reached, and attaching the new node there.
Deletion (No Children)Simply removing the node by setting its parent's pointer to null.
Deletion (Two Children)Replacing the node's value with its inorder predecessor (or successor) and then deleting that leaf node.

Performance Constraints

Balanced CaseWhen the tree is relatively symmetrical, yielding a height of log(N) and allowing optimal operations.
Degenerate CaseWhen elements are inserted in sorted order, the BST becomes a linked list with O(N) operations.
Self-BalancingAdvanced BST implementations that automatically rotate nodes to prevent the degenerate case (e.g., AVL, Red-Black).

Code example

Insert values into a binary search tree

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        node = self.root
        while True:
            if val < node.val:
                if not node.left:
                    node.left = TreeNode(val)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = TreeNode(val)
                    return
                node = node.right

tree = BST()
for value in (5, 3, 7):
    tree.insert(value)
print('Inserted: ' + ', '.join(str(v) for v in (5, 3, 7)))

struct BSTNode {
    int val;
    BSTNode *left = nullptr, *right = nullptr;
    explicit BSTNode(int x) : val(x) {}
};

class BST {
    BSTNode* root = nullptr;
public:
    void insert(int val) {
        BSTNode** link = &root;
        while (*link) link = val < (*link)->val ? &(*link)->left : &(*link)->right;
        *link = new BSTNode(val);
    }
};

class BST {
    TreeNode root;
    public void insert(int val) {
        if (root == null) root = new TreeNode(val);
        // else traverse and insert
    }
}

Inputvalues = [5, 3, 7]

OutputInserted: 5, 3, 7

Example

Run the example step by step

Output

The Danger of Imbalance

The O(log N) efficiency relies on the tree being reasonably balanced. If elements are inserted in already sorted order (e.g., 1, 2, 3, 4, 5), the tree degenerates into a linked list, dropping performance to O(N). This vulnerability necessitates self-balancing variants.

Inorder Traversal

A direct consequence of the BST invariant is that an 'inorder traversal' (visiting the left subtree, the node itself, then the right subtree) will process the elements in strictly sorted order. This makes BSTs excellent for applications needing both fast lookups and ordered iteration.