Tree Data Structures and Algorithms Cheat Sheet

Updated 2026-05-19

Trees are the foundation of hierarchical data organization in computer science — from database indexes (B-trees, Red-Black trees) to file systems, compilers, and network routing. Unlike linear structures, trees enable O(log n) search, insertion, and deletion when balanced, and support complex queries over hierarchical data. This cheat sheet covers every major tree structure and algorithm, from fundamental BST operations through advanced techniques like Heavy-Light Decomposition, Centroid Decomposition, and persistent segment trees used in competitive programming and production systems.

What This Cheat Sheet Covers

This topic spans 15 focused tables and 122 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Binary Search Tree (BST) — Core Properties and OperationsTable 2: AVL Trees — Self-Balancing via RotationsTable 3: Red-Black Trees — Production Self-Balancing BSTTable 4: Segment Trees — Range Queries and UpdatesTable 5: Fenwick Trees (Binary Indexed Trees) — Prefix Sum StructuresTable 6: Trie (Prefix Tree) — String IndexingTable 7: Tree Traversal MethodsTable 8: Lowest Common Ancestor (LCA)Table 9: Tree DP — Dynamic Programming on TreesTable 10: Euler Tour Technique — Subtree as Array RangeTable 11: Heavy-Light Decomposition (HLD)Table 12: Centroid DecompositionTable 13: Tree Diameter and Related Path ProblemsTable 14: Treap and Splay Trees — Randomized and Self-Adjusting BSTsTable 15: Sparse Table — O(1) Range Minimum / Maximum Query

Table 1: Binary Search Tree (BST) — Core Properties and Operations

The BST is the starting point for all search trees: a binary tree where every left-subtree key is smaller than the node and every right-subtree key is larger. Understanding its fundamental operations — and its worst-case degeneration — motivates every balanced-tree variant that follows.

Structure	Example	Description
BST Property	`left.key < node.key < right.key`	Every node satisfies: all keys in left subtree < node key < all keys in right subtree; enables O(log n) search on balanced trees.
Search	`if key < node: go left` `elif key > node: go right` `else: found`	Compare key with node; recurse left or right; O(log n) balanced, O(n) worst case (degenerate/linked-list tree).
Insertion	`BST.insert(5)` → walk to null leaf, place node	Search for key until null leaf; insert new node there; O(log n) average, O(n) worst.
Deletion	delete node with 2 children → replace with inorder successor	• 0 children: remove directly • 1 child: replace node with child • 2 children: replace with inorder successor (smallest in right subtree), then delete successor
Inorder Traversal	`inorder(BST)` → `[1, 3, 5, 7, 9]`	Visiting nodes left → root → right yields keys in sorted ascending order — a unique BST property.
Floor / Ceiling	`floor(6)` on `{1,3,5,7}` → `5` `ceil(6)` → `7`	Floor: largest key ≤ query. Ceiling: smallest key ≥ query. Both O(log n) via BST traversal.

Table 1: Binary Search Tree (BST) — Core Properties and Operations

Structure	Example	Description
BST Property	`left.key < node.key < right.key`	Every node satisfies: all keys in left subtree < node key < all keys in right subtree; enables O(log n) search on balanced trees.
Search	`if key < node: go left` `elif key > node: go right` `else: found`	Compare key with node; recurse left or right; O(log n) balanced, O(n) worst case (degenerate/linked-list tree).
Insertion	`BST.insert(5)` → walk to null leaf, place node	Search for key until null leaf; insert new node there; O(log n) average, O(n) worst.
Deletion	delete node with 2 children → replace with inorder successor	• 0 children: remove directly • 1 child: replace node with child • 2 children: replace with inorder successor (smallest in right subtree), then delete successor
Inorder Traversal	`inorder(BST)` → `[1, 3, 5, 7, 9]`	Visiting nodes left → root → right yields keys in sorted ascending order — a unique BST property.
Floor / Ceiling	`floor(6)` on `{1,3,5,7}` → `5` `ceil(6)` → `7`	Floor: largest key ≤ query. Ceiling: smallest key ≥ query. Both O(log n) via BST traversal.