Data StructuresIntermediate15 min readUpdated March 2025

Binary Search Trees

A Binary Search Tree (BST) is a binary tree with the ordering property: for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This enables O(log n) search, insert, and delete on balanced trees.

The BST Property

A Binary Search Tree maintains the following invariant for every node N:

- 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 holds recursively for every node in the tree. It enables efficient search: at each node, you can eliminate half the remaining tree by comparing the target with the current node's value.

Average case time complexity (balanced tree): - Search: O(log n) - Insert: O(log n) - Delete: O(log n)

Worst case (degenerate/unbalanced tree, e.g., inserting sorted data): O(n)

BST Operations: Search, Insert, Delete

The three fundamental BST operations:

python

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

    def __init__(self):
        self.root = None

    # ---- Search - O(log n) average ----
    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    # ---- Insert - O(log n) average ----
    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if node is None:
            return self.Node(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        # Duplicate: ignore (or handle as needed)
        return node

    # ---- Delete - O(log n) average ----
    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # Case 1: Leaf node
            if not node.left and not node.right:
                return None
            # Case 2: One child
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            # Case 3: Two children - replace with inorder successor
            successor = self._min_node(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
        return node

    def _min_node(self, node):
        while node.left:
            node = node.left
        return node

    def inorder(self):
        result = []
        def _inorder(node):
            if node:
                _inorder(node.left)
                result.append(node.val)
                _inorder(node.right)
        _inorder(self.root)
        return result

# Test
bst = BST()
for val in [5, 3, 7, 1, 4, 6, 8]:
    bst.insert(val)

print("Inorder:", bst.inorder())   # [1, 3, 4, 5, 6, 7, 8] (sorted!)
bst.delete(3)
print("After deleting 3:", bst.inorder())   # [1, 4, 5, 6, 7, 8]
print("Search 6:", bst.search(6) is not None)   # True

BST Validation and Floor/Ceiling

Important BST algorithms:

python

from typing import Optional

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

# ---- Validate BST ----
def is_valid_bst(root: Optional[TreeNode]) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True
        if not (min_val < node.val < max_val):
            return False
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    return validate(root, float('-inf'), float('inf'))

# ---- Floor (largest value <= target) ----
def floor_bst(root, target):
    floor = None
    while root:
        if root.val == target:
            return root.val
        elif root.val < target:
            floor = root.val   # Candidate
            root = root.right
        else:
            root = root.left
    return floor

# ---- Kth Smallest Element ----
def kth_smallest(root, k):
    stack = []
    current = root
    count = 0
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

Key Takeaways

BST property: left subtree values < node < right subtree values, enabling O(log n) operations.
Deletion of a node with two children replaces it with its inorder successor (smallest in right subtree).
Inorder traversal of a BST always produces elements in sorted order.
Worst-case BST degrades to O(n) when data is inserted in sorted order — use AVL or Red-Black trees.
Validate a BST by passing min/max bounds down the recursion, not just comparing with immediate children.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com