Binary Trees

Also Known As

TL;DR

Explanation

A binary tree has nodes with left and right children. Binary Search Tree (BST): left child < parent < right child — enables O(log n) search, insert, delete on balanced trees. Unbalanced BSTs degrade to O(n). Self-balancing trees (AVL, Red-Black) maintain O(log n) automatically. Traversals: in-order (left-root-right, gives sorted output on BST), pre-order (root-left-right), post-order (left-right-root). Heaps are specialised binary trees. PHP's SplMaxHeap/SplMinHeap are heap implementations.

Diagram

flowchart TD
    ROOT[8 root] --> L[3] & R[10]
    L --> LL[1] & LR[6]
    LR --> LRL[4] & LRR[7]
    R --> RR[14]
    RR --> RRL[13]
    INFO[BST: left < parent < right<br/>In-order: 1 3 4 6 7 8 10 13 14]
style ROOT fill:#6e40c9,color:#fff
style L fill:#1f6feb,color:#fff
style R fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Using a naive BST with sorted input — produces a degenerate linear structure; use a self-balancing tree.
• Recursive tree traversal without depth limit — deep trees cause stack overflow.
• Confusing BST (ordered) with heap (parent > children, not fully ordered) — different operations, different guarantees.
• Not understanding that B-Trees (database indexes) are not binary — B-Tree nodes can have many children.

Code Examples

// Naive BST with sorted input — degenerates to linked list:
$bst = new BST();
foreach (range(1, 10000) as $n) {
    $bst->insert($n); // Each node has only right child
}
$bst->search(9999); // O(n) — 9999 comparisons, not O(log n)

// PHP SplMinHeap — O(log n) insert and extract-min:
$heap = new SplMinHeap();
foreach ([5, 2, 8, 1, 9, 3] as $n) {
    $heap->insert($n); // O(log n)
}
while (!$heap->isEmpty()) {
    echo $heap->extract() . ' '; // 1 2 3 5 8 9 — sorted, O(n log n) total
}

References

• ↗ https://en.wikipedia.org/wiki/Binary_search_tree

Tags

Related Terms