Tree Data Structures and Algorithms Cheat Sheet

Updated 2026-05-19

🧠Study flashcards on this topic116 cards · spaced repetition→

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, 116 flashcards. 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

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

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
Successor / Predecessor	`successor(5)` in `{3,5,7,9}` → `7`	Inorder successor: smallest key > node (leftmost of right subtree or first ancestor where node is left child).
K-th Smallest	`kthSmallest(root, k=3)` → 3rd inorder element	• Augment each node with subtree size • navigate left/right in O(log n) without full traversal
Rank (Count ≤ key)	`rank(5)` → number of keys < 5	• Count nodes smaller than key • O(log n) with size-augmented BST
Height / Depth	`height = max(h(left), h(right)) + 1`	• Height: edges on longest root-to-leaf path • Balanced BST height ≈ log₂ n • degenerate ≈ n
Degenerate BST	Insert `1,2,3,4,5` in order → linked list	• Inserting sorted data without balancing creates O(n) height • motivates AVL/Red-Black trees

Table 2: AVL Trees — Self-Balancing via Rotations

AVL trees (Adelson-Velsky and Landis, 1962) were the first self-balancing BSTs. They maintain a balance factor of {-1, 0, 1} at every node, guaranteeing O(log n) height and making them ideal for read-heavy workloads where strict balance pays off.

Structure	Example	Description
Balance Factor	`bf = height(left) - height(right)` ∈ `{-1, 0, 1}`	• Every node stores `height(left subtree) − height(right subtree)` • any value outside {-1, 0, 1} triggers rebalancing

The rest of this section is part of the full cheat sheet

Table 3: Red-Black Trees — Production Self-Balancing BST

Red-Black trees underpin C++ std::map/std::set, Java TreeMap/TreeSet, and the Linux CFS scheduler. Their 5 properties allow more lenient balance than AVL — height ≤ 2log(N+1) — but require fewer rotations on modification, making them the standard choice for general-purpose sorted containers.

Structure	Example	Description
5 RB Properties	Every node: Red or Black	• Each node is red or black • Root is black • Red node has no red parent (no consecutive reds) • All root-to-NIL paths have same black-height • NIL leaves are black

The rest of this section is part of the full cheat sheet

Table 4: Segment Trees — Range Queries and Updates

Segment trees store aggregates (sum, min, max, GCD) over contiguous array ranges, enabling both range queries and point updates in O(log n). They are the workhorse of competitive programming range-query problems and also appear in database and system-level range aggregation.

Structure	Example	Description
Segment Tree Structure	Array `[1..n]` → binary tree of n nodes, size `4n`	• Node `i` stores aggregate for range `[l, r]` • left child = `2i`, right child = `2i+1` • root covers full array

The rest of this section is part of the full cheat sheet

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
Successor / Predecessor	`successor(5)` in `{3,5,7,9}` → `7`	Inorder successor: smallest key > node (leftmost of right subtree or first ancestor where node is left child).
K-th Smallest	`kthSmallest(root, k=3)` → 3rd inorder element	• Augment each node with subtree size • navigate left/right in O(log n) without full traversal
Rank (Count ≤ key)	`rank(5)` → number of keys < 5	• Count nodes smaller than key • O(log n) with size-augmented BST
Height / Depth	`height = max(h(left), h(right)) + 1`	• Height: edges on longest root-to-leaf path • Balanced BST height ≈ log₂ n • degenerate ≈ n
Degenerate BST	Insert `1,2,3,4,5` in order → linked list	• Inserting sorted data without balancing creates O(n) height • motivates AVL/Red-Black trees

Table 2: AVL Trees — Self-Balancing via Rotations

Structure	Example	Description
Balance Factor	`bf = height(left) - height(right)` ∈ `{-1, 0, 1}`	• Every node stores `height(left subtree) − height(right subtree)` • any value outside {-1, 0, 1} triggers rebalancing

Table 3: Red-Black Trees — Production Self-Balancing BST

Structure	Example	Description
5 RB Properties	Every node: Red or Black	• Each node is red or black • Root is black • Red node has no red parent (no consecutive reds) • All root-to-NIL paths have same black-height • NIL leaves are black

Table 4: Segment Trees — Range Queries and Updates

Structure	Example	Description
Segment Tree Structure	Array `[1..n]` → binary tree of n nodes, size `4n`	• Node `i` stores aggregate for range `[l, r]` • left child = `2i`, right child = `2i+1` • root covers full array