Searching

Run an inorder traversal on a **Binary Search Tree (BST)** of any size and the keys come out sorted, in `O(n)` time and `O(h)` space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's `TreeMap`, C++ `std::map`, and the conceptual model behind every database index. This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive `node.left.val < node.val` check is wrong. You will also analyze the gap between the balanced `O(log n)` and the degenerate `O(n)` chain that motivates the next lesson. In **Trees: Binary Tree Fundamentals**, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free. Next, **Balanced BST (AVL / Red-Black)** addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.

Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a `ConcurrentSkipListMap` in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a **Skip List**: a sorted linked list with a few extra express-lane pointers that turn `O(n)` search into `O(log n)` expected. This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution. In **Linked Lists (Singly)**, a search was `O(n)` because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on. Next, **Balanced BST (AVL / Red-Black)** is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.

Type the letters `a-p-p` into a search box and the autocomplete dropdown produces `apple`, `application`, `apply`, and `appoint` before you finish the next keystroke. The data structure doing that work is a **Trie** (or prefix tree), where every stored word is a path from root to a marked node and every shared prefix is shared in memory exactly once. This lesson covers the trie node layout (a `children` map plus an `isEndOfWord` flag), `insert`, `search`, and `startsWith` operations that all run in `O(m)` for a query of length `m` (independent of how many words the trie holds), and a `delete` that has to be careful not to break paths used by other words. You will also analyze the space behavior, including when a trie wins over a hash set (prefix queries, lexicographic enumeration) and when it loses (memory-tight workloads with no prefix structure to exploit). In **Hash Map (Dictionary) Basics**, you used hashing to answer 'have I seen this exact key' in `O(1)`; a trie answers a strictly richer question (any prefix lookup) by trading `O(1)` exact-match for `O(m)` traversal. **Trees: Binary Tree Fundamentals** introduced the recursive child-pointer pattern, and a trie generalizes it from two children per node to one child per alphabet symbol. With a trie in your toolkit, the curriculum moves on to graph and hash extensions that solve a different family of problems built on the same node-and-edge thinking.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.

Plain BFS finds the shortest path through a 1000x1000 grid by exploring outward in concentric circles, examining about a million cells. A* with a Manhattan-distance heuristic walks almost straight to the target and examines a few thousand. Both algorithms use the same priority-queue framework; the only difference is that A* adds a heuristic estimate to the cost function and biases the search toward the goal. That single addition is what powers GPS, game-pathfinding, and motion planning in robotics. **Advanced Search Algorithms** covers the search refinements that go beyond plain BFS and DFS. You will implement A* with the `f(n) = g(n) + h(n)` cost function, derive what makes a heuristic admissible, and prove the optimality guarantee under admissibility. Bidirectional search runs BFS from both source and target until the frontiers meet, cutting `O(b^d)` to `O(b^(d/2))`. Iterative Deepening DFS combines BFS-style completeness with DFS-style `O(d)` memory, using repeated depth-limited DFS. The lesson finishes with two specialized array searches: Jump search at `O(sqrt(n))` for sorted arrays where binary search is awkward, and interpolation search at `O(log log n)` expected for uniformly distributed keys. In **BFS & DFS (Intro)**, you wrote the basic skeletons. **Graph Algorithms (Core)** introduced Dijkstra's priority-queue relaxation, which A* generalizes by adding the heuristic. Next, **Game Theory** turns to two-player adversarial search.

Searching a sorted array of one billion elements with linear search takes up to a billion comparisons. Binary search needs about thirty. The same input, the same hardware, two algorithms with completely different scaling behavior, separated only by the assumption that the array is sorted. **Binary Search (Intro)** explains how to get that speedup and how to write the algorithm without the off-by-one errors and infinite loops that trip up almost everyone the first time. You will implement the canonical two-pointer template with `left` and `right` indices, learn why `mid = left + (right - left) / 2` matters for avoiding integer overflow, and trace the algorithm step by step on small inputs to see the search space halve each iteration. The lesson also surveys built-in support across languages (`Array.indexOf` is _not_ a binary search; Python's `bisect` is) and the most common pitfalls. In **Arrays & Strings**, you saw why indexed access on an array is `O(1)`; binary search is the first algorithm that uses that property to skip past whole regions instead of walking through them. **Big-O Notation (Upper Bound)** gave you the language `O(log n)` and the reasoning that explains why halving leads to logarithmic growth. From here you will move into **Two Pointers (Intro)**, which generalizes the same coordinated-index idea beyond exact-match searching.

Standard binary search returns an arbitrary index of a target if duplicates exist, but real problems usually want the _first_ such index, the _last_ such index, or the smallest capacity that ships every package within `D` days. Each variation needs a slightly different loop condition and return value, and getting one wrong produces an off-by-one bug or an infinite loop. **Binary Search Templates** turns those variations into a small set of memorable templates. You will work through first and last occurrence with `<=` versus `<` loop conditions, lower bound and upper bound (the templates behind Python's `bisect_left` and `bisect_right`), binary search on the answer space (the "minimize the maximum" pattern that solves Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum), and search in rotated sorted arrays where the invariant holds for exactly one half at each step. In **Binary Search (Intro)**, you wrote the canonical exact-match loop and learned why it is `O(log n)`. This lesson keeps the halving idea but switches the question from "is `target` here?" to "what is the smallest index that satisfies a monotonic predicate?". Next, **Linked List Algorithms** turns to pointer manipulation patterns.

Two Sum was a hard problem in 2010. With a hash map it becomes a six-line interview warm-up: walk the array once, and for each value `x` ask whether `target - x` is already in the map. The same shape, single-pass plus complement lookup, solves "first duplicate," "contains nearby duplicate," "longest substring without repeats," and an entire family of trade-space-for-time problems. **Hashing Techniques** catalogs those patterns. You will work through frequency counting (most/least frequent element, group anagrams via sorted-key trick), the two-sum complement template and its three-sum / four-sum extensions, existence checking and duplicate detection, index mapping where you store positions alongside values, and a first conceptual look at rolling hashes that prepare you for Rabin-Karp later. The lesson also discusses when a hash map is overkill versus when it is the obviously correct tool. In **Hash Map (Dictionary) Basics**, you saw how hashing achieves expected `O(1)` insertion and lookup. This lesson is where that constant-time primitive turns into algorithmic leverage: brute-force `O(n^2)` scans collapse into a single pass that uses the map as an oracle. From here you move into the paid track with **Sorting (Advanced)**, which trades hash-map lookups for divide-and-conquer to break the `O(n^2)` sorting barrier.

If your phone's contact list is unsorted and you are looking for Sam, the only option is to read names top to bottom until you find a match or hit the end. That brute-force scan is linear search, and it is the right algorithm in a surprising number of situations: small arrays, unsorted data, linked lists, and any case where sorting first would cost more than the search itself. **Searching (Basics)** covers linear search and its small family of variations. You will implement the standard `O(n)` scan in JavaScript and Python, learn the sentinel trick that removes a per-iteration boundary check, and adapt the same template to find the first occurrence, the last occurrence, or the first element matching a condition. The lesson also walks through linear search on linked lists, where you cannot skip ahead by index. In **Arrays & Strings**, you saw why arrays support `O(1)` random access. Searching turns that primitive into a question: how many of those accesses do you need to find a value, and can you do better than reading every one? That question motivates **Binary Search (Intro)** next, which exploits sorted order to bring the cost down to `O(log n)`.