🎬 Pattern Matching Exhaustive match, destructuring, guards, let-else — compiler-verified branching.

📝 Text version (for readers / accessibility)

• match is exhaustive — the compiler ensures every variant is handled

• Destructuring extracts fields from structs, tuples, and enums in one step

• Guards (if conditions) add extra logic to match arms

• if let and let-else provide concise single-pattern matching

• Nested patterns and @ bindings handle complex data shapes elegantly

033: At Level

Difficulty: ⭐ Level: Foundations Collect all node values at a given depth level of the tree (root = level 1).

The Problem This Solves

Sometimes you don't want to traverse an entire tree — you want a specific row. Web scrapers often navigate HTML to a specific nesting depth. Game AI evaluates board states at a fixed lookahead depth. Breadth-first search processes one level at a time. `at_level(tree, n)` is the targeted version: give me everything exactly `n` hops from the root. Combined with a loop, you get a level-order (breadth-first) traversal — one of the most important tree algorithms. This example teaches a key recursive pattern: pass a counter down through the recursion, decrementing on each level. When it hits 1, you've arrived.

The Intuition

Imagine you're descending a building by stairs. You start at level 1 (the root). Each time you take a step down, the level counter decrements. When it hits 1, you collect that node's value and stop descending. In Python:

def at_level(node, level):
 if node is None: return []
 if level == 1: return [node.val]
 return at_level(node.left, level - 1) + at_level(node.right, level - 1)

The Rust version is identical in structure — pattern matching handles the two base cases cleanly:

Tree::Leaf => vec![],        // no node here
Tree::Node(...) if level == 1 => vec![v.clone()]  // arrived

How It Works in Rust

fn at_level<T: Clone>(tree: &Tree<T>, level: usize) -> Vec<T> {
 match tree {
     Tree::Leaf => vec![],  // ran off the edge

     Tree::Node(l, v, r) => {
         if level == 1 {
             vec![v.clone()]  // arrived at target depth
         } else {
             // Go one level deeper in both subtrees
             let mut result = at_level(l, level - 1);
             result.extend(at_level(r, level - 1));
             result
         }
     }
 }
}

For the sample tree:

    a     ← level 1
   / \
  b   c   ← level 2
 / \
d   e     ← level 3

`at_level(&t, 1)` → `['a']`
`at_level(&t, 2)` → `['b', 'c']`
`at_level(&t, 3)` → `['d', 'e']`
`at_level(&t, 4)` → `[]`

The full breadth-first traversal collects all levels using a queue — the iterative `levels()` function in the code shows this pattern.

What This Unlocks

BFS skeleton: loop over `at_level(t, 1)`, `at_level(t, 2)`, ... for full level-order traversal.
Game AI: evaluate all positions at a fixed search depth (minimax, alpha-beta pruning).
Tree visualization: render one row at a time for console or UI display.

Key Differences

Concept	OCaml	Rust
Depth counter	`at_level tree n` decrement n	`at_level(tree, level)` decrement level
Base case	`Leaf -> []`	`Tree::Leaf => vec![]`
BFS via queue	`Queue.push`	`Vec` as queue (`push`/`remove(0)`) or `VecDeque`
`usize` underflow	N/A (int)	Use `usize` — safe since `level == 1` stops before `0`

// At Level — 99 Problems #33
// Collect the nodes at a given level of a binary tree.
// Root is at level 1.

#[derive(Debug, PartialEq, Clone)]
enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

impl<T: Clone> Tree<T> {
    fn leaf() -> Self { Tree::Leaf }
    fn node(l: Tree<T>, v: T, r: Tree<T>) -> Self {
        Tree::Node(Box::new(l), v, Box::new(r))
    }
}

fn at_level<T: Clone>(tree: &Tree<T>, level: usize) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(l, v, r) => {
            if level == 1 {
                vec![v.clone()]
            } else {
                let mut result = at_level(l, level - 1);
                result.extend(at_level(r, level - 1));
                result
            }
        }
    }
}

/// Breadth-first traversal returning all levels.
fn levels<T: Clone>(tree: &Tree<T>) -> Vec<Vec<T>> {
    let mut result = Vec::new();
    let mut queue = vec![tree];
    while !queue.is_empty() {
        let mut next_queue = Vec::new();
        let mut level_vals = Vec::new();
        for t in queue {
            if let Tree::Node(l, v, r) = t {
                level_vals.push(v.clone());
                if !matches!(l.as_ref(), Tree::Leaf) {
                    next_queue.push(l.as_ref());
                }
                if !matches!(r.as_ref(), Tree::Leaf) {
                    next_queue.push(r.as_ref());
                }
            }
        }
        if !level_vals.is_empty() {
            result.push(level_vals);
        }
        queue = next_queue;
    }
    result
}

fn sample_tree() -> Tree<char> {
    //        a          level 1
    //       / \
    //      b   c        level 2
    //     / \
    //    d   e          level 3
    Tree::node(
        Tree::node(
            Tree::node(Tree::leaf(), 'd', Tree::leaf()),
            'b',
            Tree::node(Tree::leaf(), 'e', Tree::leaf()),
        ),
        'a',
        Tree::node(Tree::leaf(), 'c', Tree::leaf()),
    )
}

fn main() {
    let t = sample_tree();
    println!("Level 1: {:?}", at_level(&t, 1)); // [a]
    println!("Level 2: {:?}", at_level(&t, 2)); // [b, c]
    println!("Level 3: {:?}", at_level(&t, 3)); // [d, e]
    println!("Level 4: {:?}", at_level(&t, 4)); // []

    println!("All levels: {:?}", levels(&t));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_level_1() {
        assert_eq!(at_level(&sample_tree(), 1), vec!['a']);
    }

    #[test]
    fn test_level_2() {
        assert_eq!(at_level(&sample_tree(), 2), vec!['b', 'c']);
    }

    #[test]
    fn test_level_3() {
        assert_eq!(at_level(&sample_tree(), 3), vec!['d', 'e']);
    }

    #[test]
    fn test_level_beyond() {
        assert_eq!(at_level(&sample_tree(), 5), vec![]);
    }

    #[test]
    fn test_all_levels_count() {
        let all = levels(&sample_tree());
        assert_eq!(all.len(), 3);
        assert_eq!(all[0], vec!['a']);
        assert_eq!(all[1], vec!['b', 'c']);
        assert_eq!(all[2], vec!['d', 'e']);
    }
}

(* At Level *)
(* OCaml 99 Problems #33 *)

(* Implementation for example 33 *)

(* Tests *)
let () =
  (* Add tests *)
  print_endline "✓ OCaml tests passed"