# Data Structures Algorithms
All Data Structures Algorithms notes →1 — Tree Fundamentals
Root, parent, child, leaf, depth vs. height, and the recursively-defined structure — general vs. binary trees, the four traversal orders, and pointer- vs. array-based representation — that every later tree chapter assumes without re-explaining.
10 — Suffix Trie
Suffix-indexed trie variant for substring and pattern-matching queries.
11 — Heap
Binary heap structure (array-backed complete tree) and the sift-up/sift-down operations behind heapify — the weaker parent-children invariant that makes find-min cheap, why completeness makes array representation waste nothing, and heapq's push/pop/heapify/heappushpop/heapreplace in practice.
12 — Priority Queue
Priority queue as an abstract interface — insert with a priority, extract the highest-priority item — and why a binary heap, not a sorted list or a balanced BST, is usually the implementation of choice; includes full top-K and k-way merge worked examples.
2 — Binary Trees
Binary tree node structure and traversal: preorder, inorder, and postorder — each recursive and iterative (postorder's two-stack trick for the trickiest case) — plus level-order BFS via a queue, recursive height/depth, and when each traversal order actually matters in practice.
3 — Binary Search Trees
The BST ordering invariant and its duplicates-go-right convention, why search/insert/delete are O(h) rather than unconditionally O(log n), why inorder traversal always yields sorted order, the three delete cases including the inorder-successor splice, why sorted-input insertion degenerates a BST into a linked list, and the range-bound fix for the classic buggy Validate BST check.
4 — AVL Trees
Height-balanced BST with rotation-based rebalancing that guarantees O(log n) operations.
5 — Red-Black Trees
Color-based self-balancing BST used by most production ordered-map implementations, and how it trades stricter balance for cheaper rebalancing.
6 — Segment Trees
Binary tree over array ranges trading prefix sum's O(1) query for O(log n) — in exchange for O(log n) point updates with no rebuild, ever.
7 — Fenwick Trees (BIT)
Binary Indexed Tree for O(log n) prefix-sum queries and point updates with a much smaller constant than a segment tree.
8 — Interval Trees
Augmented BST ordered by interval low-endpoint, storing each subtree's max high-endpoint (max_end) to prune subtrees that provably can't overlap a query — cutting overlap search from O(n) brute force to O(log n + k), and why max_end is the one field that makes the pruning possible.
9 — Trie
Prefix tree structure that makes 'does any word start with this' as cheap as exact-match lookup — insert/search/startsWith in O(L), autocomplete via DFS, and the memory trade-off against a plain hash set.