Data Structures, Algorithms and Programming Patterns · Part 4 of 9

Data Structures and Algorithms, Part 4: Trees, Heaps and Tries

Lines are not enough for data that branches, nests or needs the smallest item fast. This part introduces trees: how to walk them, how a search tree finds things in about log n steps, how a heap keeps the smallest value on top, and how a trie answers questions about prefixes.

1. What a tree is

So far the structures in this series were lines: arrays, lists, stacks, queues. A line has a first item, a last item, and everything else sits in between. Many things in the real world are not lines. They branch. A tree is the data structure for things that branch.

Here are the words you need. They are used in every tree discussion, so learn them now.

• Node: one box in the tree. It holds a value and links to its children.
• Root: the single node at the top. It has no parent.
• Parent and child: a node directly above another is its parent; the ones directly below are its children.
• Leaf: a node with no children.
• Depth of a node: how many steps you take going down from the root to reach it. The root has depth 0.
• Height of the tree: the depth of its deepest node. Books differ on whether to count steps or nodes. In the code below, "max depth" counts the nodes on the longest path, so a single node has max depth 1 and an empty tree has 0. Both ways are fine, just be clear about which one you use.
• Subtree: any node together with everything below it. Every child of a node is the root of its own smaller tree.

In this part we mostly use binary trees, where each node has at most two children: a left one and a right one. The node is small. It stores a value and two links, and a link is either another node or null (nothing there).

class TreeNode(
    val value: Int,
    var left: TreeNode? = null,
    var right: TreeNode? = null
)

// Print the tree turned on its side: right child on top, root at the left.
fun printSideways(node: TreeNode?, depth: Int = 0) {
    if (node == null) return
    printSideways(node.right, depth + 1)
    println("    ".repeat(depth) + node.value)
    printSideways(node.left, depth + 1)
}

fun main() {
    //         8
    //       /   \
    //      3     10
    //     / \      \
    //    1   6      14
    val root = TreeNode(
        8,
        TreeNode(3, TreeNode(1), TreeNode(6)),
        TreeNode(10, null, TreeNode(14))
    )
    printSideways(root)
}

An empty tree is simply null. That one fact makes the code in this part short: every function starts by asking "is this node null?", and that is the stopping point of the recursion.

2. Walking a tree depth first

To traverse a tree means to visit every node once. There are two big families. The first goes deep before it goes wide: it follows one branch to the bottom, then backs up and tries the next. It is called depth-first search (DFS).

For a binary tree the recursion is three lines long. The only choice is when you handle the current node compared with its two subtrees. That gives three famous orders:

• Pre-order: node, then left, then right. Good for copying a tree or printing it as an outline.
• In-order: left, then node, then right. On a search tree this gives sorted output (see below).
• Post-order: left, then right, then node. Good when you need the children's answers first, such as deleting a tree or computing sizes.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun preOrder(node: TreeNode?, out: MutableList<Int> = mutableListOf()): List<Int> {
    if (node == null) return out
    out.add(node.value)          // visit the node first
    preOrder(node.left, out)
    preOrder(node.right, out)
    return out
}

fun inOrder(node: TreeNode?, out: MutableList<Int> = mutableListOf()): List<Int> {
    if (node == null) return out
    inOrder(node.left, out)
    out.add(node.value)          // visit the node in the middle
    inOrder(node.right, out)
    return out
}

fun postOrder(node: TreeNode?, out: MutableList<Int> = mutableListOf()): List<Int> {
    if (node == null) return out
    postOrder(node.left, out)
    postOrder(node.right, out)
    out.add(node.value)          // visit the node last
    return out
}

fun main() {
    val root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(6, TreeNode(5), TreeNode(7))
    )
    println("pre-order : ${preOrder(root)}")
    println("in-order  : ${inOrder(root)}")
    println("post-order: ${postOrder(root)}")
    println("empty tree: ${inOrder(null)}")
}

Cost. Each node is visited once, so the time is O(n). The recursion uses the call stack, which is as deep as the tree is tall. Call that height h: the extra space is O(h). For a nicely balanced tree h is about log n; for a tree that is just a long chain, h is n.

3. Walking a tree level by level

The second family goes wide first. It visits the root, then all nodes at depth 1, then all nodes at depth 2, and so on. This is breadth-first search (BFS), also called level-order traversal.

Recursion does not give this order naturally. We use a queue (Part 3): first in, first out. Put the root in the queue. Then repeat: take the front node, visit it, and put its children at the back. Because children join the back, a whole level is processed before the next one starts.

To report the levels separately, we note the queue size at the start of each round. That many nodes are exactly the current level.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    if (root == null) return result
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val levelSize = queue.size          // how many nodes are in this level
        val level = mutableListOf<Int>()
        repeat(levelSize) {
            val node = queue.removeFirst()
            level.add(node.value)
            node.left?.let { queue.addLast(it) }
            node.right?.let { queue.addLast(it) }
        }
        result.add(level)
    }
    return result
}

fun main() {
    val root = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7))
    )
    println(levelOrder(root))     // [[3], [9, 20], [15, 7]]
    println(levelOrder(null))     // []
}

Which walk should I pick?

4. Height, size, mirror and comparing trees

Most tree questions follow one habit. Ask: if I trust the answer for my left child and my right child, how do I build the answer for me? Then add the base case: an empty tree. Let us practise that habit four times.

• Size (number of nodes): 1 + size(left) + size(right). Empty tree: 0.
• Max depth (nodes on the longest root-to-leaf path): 1 + max(depth(left), depth(right)). Empty tree: 0.
• Mirror (swap left and right everywhere): swap the two children, then mirror each of them.
• Same tree: two trees are equal if both are empty, or both roots match and their left subtrees match and their right subtrees match.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun size(node: TreeNode?): Int =
    if (node == null) 0 else 1 + size(node.left) + size(node.right)

fun maxDepth(node: TreeNode?): Int =
    if (node == null) 0 else 1 + maxOf(maxDepth(node.left), maxDepth(node.right))

// Build a new mirrored tree and leave the original alone.
fun mirror(node: TreeNode?): TreeNode? {
    if (node == null) return null
    return TreeNode(node.value, mirror(node.right), mirror(node.left))
}

fun sameTree(a: TreeNode?, b: TreeNode?): Boolean {
    if (a == null && b == null) return true
    if (a == null || b == null) return false
    return a.value == b.value && sameTree(a.left, b.left) && sameTree(a.right, b.right)
}

fun inOrder(node: TreeNode?): List<Int> =
    if (node == null) emptyList() else inOrder(node.left) + node.value + inOrder(node.right)

fun main() {
    val t = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
    println("size = ${size(t)}")                  // 4
    println("max depth = ${maxDepth(t)}")         // 3
    val m = mirror(t)
    println("in-order before: ${inOrder(t)}")     // [4, 2, 1, 3]
    println("in-order mirror: ${inOrder(m)}")     // [3, 1, 2, 4]
    println("t same as t? ${sameTree(t, t)}")     // true
    println("t same as mirror? ${sameTree(t, m)}")  // false
    println("empty same as empty? ${sameTree(null, null)}")  // true
    println("single node depth = ${maxDepth(TreeNode(9))}")   // 1
}

Check the habit on the weird shapes too: an empty tree, a single node, and a skewed tree, where every node has only one child so the tree looks like a linked list. A good solution handles all three without special code.

5. Binary search trees

A plain binary tree puts no rules on where values go. A binary search tree (BST) adds one rule that makes searching fast:

For every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

Insert, search and why in-order is sorted

Insert works like search: walk down until you fall off the tree, and put the new node in that empty spot. Now think about in-order traversal (left, node, right). All smaller values are on the left, so they come first, then the node, then all larger values. That holds at every node, so the whole output comes out sorted. A BST gives you sorted data almost for free.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Bst {
    var root: TreeNode? = null
    var size = 0
        private set

    // Returns false if the value was already there.
    fun insert(value: Int): Boolean {
        val newNode = TreeNode(value)
        var cur = root
        if (cur == null) { root = newNode; size++; return true }
        while (true) {
            if (value == cur!!.value) return false
            if (value < cur.value) {
                if (cur.left == null) { cur.left = newNode; size++; return true }
                cur = cur.left
            } else {
                if (cur.right == null) { cur.right = newNode; size++; return true }
                cur = cur.right
            }
        }
    }

    fun contains(value: Int): Boolean {
        var cur = root
        while (cur != null) {
            cur = when {
                value == cur.value -> return true
                value < cur.value -> cur.left
                else -> cur.right
            }
        }
        return false
    }

    fun toSortedList(): List<Int> {
        val out = mutableListOf<Int>()
        fun walk(n: TreeNode?) {
            if (n == null) return
            walk(n.left); out.add(n.value); walk(n.right)
        }
        walk(root)
        return out
    }

    fun height(): Int {
        fun h(n: TreeNode?): Int = if (n == null) 0 else 1 + maxOf(h(n.left), h(n.right))
        return h(root)
    }
}

fun main() {
    val tree = Bst()
    for (x in listOf(8, 3, 10, 1, 6, 14, 4, 7, 6)) {
        val added = tree.insert(x)
        if (!added) println("$x was already in the tree")
    }
    println("sorted: ${tree.toSortedList()}")
    println("contains 7? ${tree.contains(7)}")
    println("contains 5? ${tree.contains(5)}")
    println("size=${tree.size} height=${tree.height()}")
}

Fast when balanced, slow when skewed

Search, insert and "does it contain" all walk one path from the root down. The cost is the height h. If the tree is balanced (both sides about the same size), each step halves the problem, so h is about log n and the operations are O(log n). A million values need only about 20 steps.

But the shape depends on insert order. Insert 1, 2, 3, 4, 5 in that order and each value goes to the right of the last. You get a chain, the tree is skewed, the height is n, and every operation is O(n). That is no better than a list.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun insert(root: TreeNode?, value: Int): TreeNode {
    if (root == null) return TreeNode(value)
    if (value < root.value) root.left = insert(root.left, value)
    else if (value > root.value) root.right = insert(root.right, value)
    return root
}

fun height(n: TreeNode?): Int = if (n == null) 0 else 1 + maxOf(height(n.left), height(n.right))

// Insert the middle first, then the middles of each half: a balanced order.
fun balancedOrder(lo: Int, hi: Int, out: MutableList<Int>) {
    if (lo > hi) return
    val mid = (lo + hi) / 2
    out.add(mid)
    balancedOrder(lo, mid - 1, out)
    balancedOrder(mid + 1, hi, out)
}

fun main() {
    val n = 1000
    var skewed: TreeNode? = null
    for (x in 1..n) skewed = insert(skewed, x)          // sorted input

    val order = mutableListOf<Int>()
    balancedOrder(1, n, order)
    var balanced: TreeNode? = null
    for (x in order) balanced = insert(balanced, x)     // same values, smart order

    println("values: $n")
    println("height when inserted in sorted order: ${height(skewed)}")
    println("height when inserted middle-first   : ${height(balanced)}")
}

Checking that a tree really is a BST

A common mistake is to check only that each node is bigger than its left child and smaller than its right child. That is not enough. In the tree below every parent-child pair looks fine, yet 3 sits in the right subtree of 5, so it breaks the rule.

The fix is to carry down a range of allowed values. The root may be anything. Going left, the upper limit becomes the parent's value; going right, the lower limit becomes the parent's value. Every node must be strictly inside its range.

fun isValidBst(node: TreeNode?, low: Int? = null, high: Int? = null): Boolean {
    if (node == null) return true
    if (low != null && node.value <= low) return false
    if (high != null && node.value >= high) return false
    return isValidBst(node.left, low, node.value) &&
           isValidBst(node.right, node.value, high)
}

You will write this one yourself in the practice section. It is O(n) time and O(h) space.

6. Balanced trees in the real world

Since a skewed tree is slow, people invented trees that keep themselves balanced. After each insert or delete they check the shape and, if one side has become too tall, they fix it with small local changes called rotations. A rotation lifts one node up and pushes another down while keeping the BST rule true.

Two well-known designs are the AVL tree (very strict about balance, so lookups are fastest) and the red-black tree (a bit looser, so inserts and deletes do less repair work). You do not need to implement them now. It is enough to know that they guarantee O(log n) for search, insert and delete, even in the worst case.

The good news is that you rarely have to write one. Kotlin and Java ship a red-black tree as java.util.TreeMap (and TreeSet for just keys). It keeps its keys sorted and offers operations a hash map cannot: smallest and largest key, "the next key above this one", and "all keys between a and b".

import java.util.TreeMap

fun main() {
    val scores = TreeMap<Int, String>()
    scores[70] = "Mia"
    scores[95] = "Omar"
    scores[82] = "Lena"
    scores[60] = "Ken"

    println("in key order : $scores")
    println("lowest       : ${scores.firstKey()} ${scores.firstEntry().value}")
    println("highest      : ${scores.lastKey()} ${scores.lastEntry().value}")
    println("first >= 80  : ${scores.ceilingKey(80)}")     // 82
    println("last  <= 80  : ${scores.floorKey(80)}")       // 70
    println("between 65..90: ${scores.subMap(65, true, 90, true)}")
}

7. Heaps and priority queues

Sometimes you do not need everything sorted. You only need the smallest (or largest) item, again and again, while new items keep arriving. Think of a hospital emergency room: the most urgent patient is seen next, no matter who arrived first. That is a priority queue: a queue where the item with the best priority leaves first.

The standard way to build one is a heap. A (min-)heap is a binary tree with two rules:

1. Heap rule: every parent is smaller than or equal to its children. So the smallest value is always at the root.
2. Shape rule: the tree is filled level by level, left to right, with no gaps. This keeps it short, with height about log n.

The array trick

Since the shape has no gaps, we do not need node objects or links. We just use an array and compute where the relatives are from the index i:

Check with the picture: index 1 holds 4. Its children are at 3 and 4, which hold 9 and 5. Its parent is at (1-1)/2 = 0, which holds 2. It works.

Push: add at the end, then sift up

Put the new value in the first free spot (the end of the array). That keeps the shape rule, but the value might be smaller than its parent. So sift up: while it is smaller than its parent, swap them. It climbs at most the height of the tree, so push is O(log n).

Pop: take the root, move the last item up, then sift down

The smallest value is at index 0. Remove it, then move the very last item into the root's place (to keep the shape rule). Now the root may be too big. So sift down: swap it with its smaller child until neither child is smaller. Again at most one trip down the tree: O(log n). Peeking at the smallest value is O(1).

class MinHeap {
    private val a = ArrayList<Int>()

    val size: Int get() = a.size
    fun isEmpty() = a.isEmpty()

    fun peek(): Int {
        if (a.isEmpty()) throw NoSuchElementException("heap is empty")
        return a[0]
    }

    fun push(x: Int) {
        a.add(x)                  // put it in the first free spot
        siftUp(a.size - 1)
    }

    fun pop(): Int {
        if (a.isEmpty()) throw NoSuchElementException("heap is empty")
        val top = a[0]
        val last = a.removeAt(a.size - 1)
        if (a.isNotEmpty()) {
            a[0] = last           // move the last item to the root
            siftDown(0)
        }
        return top
    }

    private fun siftUp(start: Int) {
        var i = start
        while (i > 0) {
            val parent = (i - 1) / 2
            if (a[i] >= a[parent]) break
            swap(i, parent)
            i = parent
        }
    }

    private fun siftDown(start: Int) {
        var i = start
        while (true) {
            val left = 2 * i + 1
            val right = 2 * i + 2
            var smallest = i
            if (left < a.size && a[left] < a[smallest]) smallest = left
            if (right < a.size && a[right] < a[smallest]) smallest = right
            if (smallest == i) break
            swap(i, smallest)
            i = smallest
        }
    }

    private fun swap(i: Int, j: Int) {
        val t = a[i]; a[i] = a[j]; a[j] = t
    }

    override fun toString() = a.toString()
}

fun main() {
    val heap = MinHeap()
    for (x in listOf(9, 4, 7, 1, 8, 2)) {
        heap.push(x)
        println("push $x -> $heap")
    }
    print("pop order:")
    while (!heap.isEmpty()) print(" ${heap.pop()}")
    println()
}

Pushing n items and popping them all is itself a sorting method called heap sort: O(n log n) time. Real heap sort does it inside one array without extra space, but the idea is the same.

The ready-made one: PriorityQueue

In everyday code use java.util.PriorityQueue. It is a min-heap by default. To change the order, hand it a comparator: a small rule that says which of two items comes first. Use compareBy for the field to sort on, or reverse it to get a max-heap.

import java.util.PriorityQueue

data class Task(val name: String, val priority: Int)

// The k largest numbers, using a min-heap that never grows past k items.
fun kLargest(nums: List<Int>, k: Int): List<Int> {
    val heap = PriorityQueue<Int>()          // smallest of the kept ones is on top
    for (x in nums) {
        heap.add(x)
        if (heap.size > k) heap.poll()       // throw away the smallest
    }
    return heap.sortedDescending()
}

fun heapSort(nums: List<Int>): List<Int> {
    val heap = PriorityQueue<Int>(nums)
    val out = mutableListOf<Int>()
    while (heap.isNotEmpty()) out.add(heap.poll())
    return out
}

fun main() {
    // 1. Min-heap by default
    val mins = PriorityQueue<Int>()
    mins.addAll(listOf(5, 1, 4))
    println("smallest first: ${mins.poll()}")

    // 2. Max-heap by reversing the order
    val maxs = PriorityQueue<Int>(compareByDescending { it })
    maxs.addAll(listOf(5, 1, 4))
    println("largest first : ${maxs.poll()}")

    // 3. Order custom objects with a comparator
    val tasks = PriorityQueue<Task>(compareBy { it.priority })
    tasks.add(Task("write report", 3))
    tasks.add(Task("fix crash", 1))
    tasks.add(Task("reply to mail", 2))
    while (tasks.isNotEmpty()) println("do: ${tasks.poll().name}")

    // 4. Top-k and heap sort
    val data = listOf(7, 2, 9, 4, 11, 3, 8)
    println("top 3 : ${kLargest(data, 3)}")
    println("sorted: ${heapSort(data)}")
}

8. Tries: trees for words

How does a phone keyboard suggest words while you type? It needs to find all words that start with what you have typed so far. Scanning every word in the dictionary for each key press would be slow. A trie (say "try", from retrieval), also called a prefix tree, is built for exactly this.

In a trie each node stands for a letter, and a path from the root spells a prefix. Words that share a beginning share the same nodes. A flag on a node says "a word ends here". Below we store car, cat, can and do. The nodes marked with a star end a word.

Each node keeps a map from letter to child node. Operations walk one letter at a time:

• insert(word): follow the letters, creating missing nodes, and mark the last node as a word end.
• search(word): follow the letters; the word exists only if the path exists and the last node is marked as a word end. (Otherwise you only found a prefix: ca is on the path but not a stored word.)
• startsWith(prefix): follow the letters; it only needs the path to exist.

class TrieNode {
    val next = HashMap<Char, TrieNode>()
    var isWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var cur = root
        for (c in word) cur = cur.next.getOrPut(c) { TrieNode() }
        cur.isWord = true
    }

    private fun find(prefix: String): TrieNode? {
        var cur = root
        for (c in prefix) cur = cur.next[c] ?: return null
        return cur
    }

    fun search(word: String): Boolean = find(word)?.isWord == true

    fun startsWith(prefix: String): Boolean = find(prefix) != null

    // Autocomplete: every stored word that begins with the prefix, in alphabetical order.
    fun wordsWithPrefix(prefix: String): List<String> {
        val start = find(prefix) ?: return emptyList()
        val out = mutableListOf<String>()
        fun collect(node: TrieNode, soFar: String) {
            if (node.isWord) out.add(soFar)
            for (c in node.next.keys.sorted()) collect(node.next.getValue(c), soFar + c)
        }
        collect(start, prefix)
        return out
    }
}

fun main() {
    val trie = Trie()
    for (w in listOf("car", "cat", "can", "candy", "do", "dog")) trie.insert(w)

    println("search car    : ${trie.search("car")}")
    println("search ca     : ${trie.search("ca")}")        // a prefix, not a word
    println("startsWith ca : ${trie.startsWith("ca")}")
    println("startsWith x  : ${trie.startsWith("x")}")
    println("ca* -> ${trie.wordsWithPrefix("ca")}")
    println("do* -> ${trie.wordsWithPrefix("do")}")
    println("z*  -> ${trie.wordsWithPrefix("z")}")
}

Cost. Let L be the length of the word. Insert, search and startsWith take O(L) time, and notably they do not depend on how many words are stored. The price is memory: the trie holds up to one node per letter stored, so space is O(total letters). A hash set also finds a whole word in about O(L) time, but it cannot answer prefix questions without scanning everything. That is where the trie wins.

9. Complexity at a glance

Here are the costs from this part in one place. n is the number of items, h the tree height, k the number you keep, and L the word length.

Notice the theme: a tree turns a long line into a short, branching path. Going from n steps to about log n is the whole point, and the catch is always the same, namely keeping the tree balanced.

10. Practice

Five exercises, from a first recursion on a tree to a data structure of your own. Each one has edge cases on purpose: an empty tree, a single node and a skewed tree. Think about those before you run the tests.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun maxDepth(root: TreeNode?): Int {
    TODO("1 + the larger depth of the two children")
}

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun maxDepth(root: TreeNode?): Int {
    if (root == null) return 0
    return 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
}

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun levelOrder(root: TreeNode?): List<List<Int>> {
    TODO("use a queue; process one whole level per round")
}

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    if (root == null) return result
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val level = mutableListOf<Int>()
        repeat(queue.size) {
            val node = queue.removeFirst()
            level.add(node.value)
            node.left?.let { queue.addLast(it) }
            node.right?.let { queue.addLast(it) }
        }
        result.add(level)
    }
    return result
}

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun isValidBst(root: TreeNode?): Boolean {
    TODO("carry a low and a high limit down the tree")
}

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun isValidBst(root: TreeNode?): Boolean {
    fun check(node: TreeNode?, low: Int?, high: Int?): Boolean {
        if (node == null) return true
        if (low != null && node.value <= low) return false
        if (high != null && node.value >= high) return false
        return check(node.left, low, node.value) && check(node.right, node.value, high)
    }
    return check(root, null, null)
}

fun kLargest(nums: List<Int>, k: Int): List<Int> {
    TODO("keep a min-heap of size k, throw away the smallest when it grows")
}

fun kLargest(nums: List<Int>, k: Int): List<Int> {
    if (k <= 0) return emptyList()
    val heap = java.util.PriorityQueue<Int>()
    for (x in nums) {
        heap.add(x)
        if (heap.size > k) heap.poll()
    }
    return heap.sortedDescending()
}

class TrieNode {
    val next = HashMap<Char, TrieNode>()
    var isWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        TODO("walk the letters, create missing nodes, mark the end")
    }

    fun search(word: String): Boolean {
        TODO("path must exist and end on a word")
    }

    fun startsWith(prefix: String): Boolean {
        TODO("path must exist")
    }
}

class TrieNode {
    val next = HashMap<Char, TrieNode>()
    var isWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var cur = root
        for (c in word) cur = cur.next.getOrPut(c) { TrieNode() }
        cur.isWord = true
    }

    private fun find(prefix: String): TrieNode? {
        var cur = root
        for (c in prefix) cur = cur.next[c] ?: return null
        return cur
    }

    fun search(word: String): Boolean = find(word)?.isWord == true

    fun startsWith(prefix: String): Boolean = find(prefix) != null
}

11. Takeaways

• Most tree code is: handle the empty tree, trust the answers from both children, combine them.
• Pick DFS when answers come from subtrees, BFS when depth or levels matter.
• A BST is only fast if it stays balanced; use TreeMap or TreeSet instead of writing your own.
• Validate a BST with a range, not by comparing a node with its parent alone.
• A heap is a tree in an array: children at 2i+1 and 2i+2, parent at (i-1)/2.
• Use a size-k heap for top-k; use a trie when you need prefix queries.
• Next up: graphs, where nodes can connect to any other node and trees are just a special case.