Binary search trees

A binary search tree (BST) is a binary tree with an ordering rule: for every node, all values in its left subtree are smaller than the node's value and all values in its right subtree are larger. The rule applies to whole subtrees, not just to direct children.

Because of the rule, finding a value is like binary search: compare with the node and go left or right, discarding a whole subtree each step. The cost is the height h of the tree. If the tree is balanced, h is about log2(n), so a million values need about 20 comparisons. If values are inserted in sorted order, the tree becomes a chain and h is n.

Self-balancing BSTs such as red-black trees and AVL trees rotate nodes after inserts and deletes to keep the height O(log n) in the worst case. Interviews usually ask you to work with a plain BST but expect you to know this.

1. 1Search: start at the root. If the target equals the node, stop. If smaller, go left; if larger, go right. Reaching an empty child means the value is not present.
2. 2Insert: search for the value; the empty spot where the search falls off the tree is exactly where the new node goes, as a leaf.
3. 3Delete a leaf: remove it. Delete a node with one child: replace it with that child.
4. 4Delete a node with two children: find its inorder successor (the smallest value in its right subtree), copy that value into the node, then delete the successor, which has at most one child.
5. 5Validate: carry an allowed range (low, high) down the tree. The root may be anything; a left child narrows high to the parent's value, a right child narrows low. Any value outside its range breaks the BST.

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

def search(node, target):
    while node and node.val != target:
        node = node.left if target < node.val else node.right
    return node                       # None if not found

def insert(node, val):
    if node is None:
        return TreeNode(val)          # the empty spot is where it belongs
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node

def is_valid_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    if not (low < node.val < high):   # must fit the range set by all ancestors
        return False
    return (is_valid_bst(node.left, low, node.val) and
            is_valid_bst(node.right, node.val, high))

Search walks a single path, so it costs O(h). Insert reuses that path and attaches a leaf, ignoring duplicates. Validation passes the allowed range down instead of only comparing with the direct parent, which catches violations deep in a subtree. The TreeNode class (val, left, right) is the node shape used on every tree page.

Cost: Search, insert and delete are O(h): O(log n) balanced, O(n) worst case for a plain BST. Self-balancing trees guarantee O(log n). Inorder iteration is O(n).