Tree / Binary Search Tree

Branching hierarchy.

A tree starts at a root and branches into child nodes, like a family tree or folder structure. A binary tree gives each node at most two children (left and right). A binary search tree (BST) adds a rule: everything to the left of a node is smaller, everything to the right is larger.

• Root — the top node; leaf — a node with no children.
• BST rule lets you find a value by going left/right, halving the search each step.

Traversals and complexity.

In-order    left, node, right   → sorted output for a BST
Pre-order   node, left, right   → copy / serialize
Post-order  left, right, node   → delete / evaluate
Level-order breadth-first (uses a queue)

Search/insert/delete are O(h) where h is the height. A balanced tree has h ≈ log n; a degenerate (sorted-insert) tree becomes a linked list with h = n and O(n) operations.

Balancing and beyond.

• Self-balancing BSTs — AVL (strict balance, faster lookups) and Red–Black (looser, fewer rotations on write; used by TreeMap/std::map).
• B-trees / B+ trees — high-fanout trees for disk/database indexes, minimizing expensive I/O.
• Deletion cases — leaf, one child, or two children (replace with in-order successor/predecessor).
• Related trees — segment trees and Fenwick (BIT) for range queries; tries for strings; heaps for priority.