Trees and Search Trees

A tree is a connected acyclic graph. A rooted tree gives every non-root node one parent. Depth counts edges from the root; height is the maximum remaining depth to a leaf under the convention used here.

Binary search tree invariant

For every node with key k:

• keys in its left subtree are less than k;
• keys in its right subtree are greater than k;
• a separate policy handles duplicates.

Search, insertion, and removal take O(h) time for height h. A balanced tree has h = Θ(log n); an ordinary BST can degenerate to h = Θ(n).

graph TD
    A[8] --> B[3]
    A --> C[10]
    B --> D[1]
    B --> E[6]
    E --> F[4]
    E --> G[7]
    C --> H[14]
    H --> I[13]

An in-order traversal visits the keys in sorted order. Pre-order is useful for serialization and structural copying; post-order processes children before a parent.

Balanced variants

AVL and red-black trees maintain different balance invariants using rotations. Both guarantee logarithmic height. B-trees and related structures use high branching factors to reduce storage-page accesses.

Exercises

1. List the in-order, pre-order, and post-order traversals above.
2. Show a key insertion sequence that creates a linear-height BST.
3. Explain why a local rotation preserves sorted order.