Binary trees, BSTs and order statistics

A binary tree permits at most two children; a BST adds ordering. Decide how duplicates are represented. Checking only immediate children does not validate a BST: descendants must respect ancestor bounds.

Search follows one root-to-node path and costs O(h). Sorted insertion can form a chain with h=n. Inorder traversal produces sorted keys. Deleting a node handles leaf, one-child and two-child cases; the latter can use a successor/predecessor and remove its original node.

Subtree-size augmentation supports rank and select. Rotations and edits must update metadata, not merely links. Without balancing, order-statistic operations can still become linear.

def valid_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None: return True
    key, left, right = node
    return (lo < key < hi and valid_bst(left, lo, key)
            and valid_bst(right, key, hi))
assert not valid_bst((10,(5,None,(12,None,None)),None))