ExamplesBy LevelBy TopicLearning Paths
033 Intermediate
← 032034 →

033 — Collect the Nodes at a Given Level

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "033 — Collect the Nodes at a Given Level" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Collecting all nodes at a specific depth (OCaml 99 Problems #33) — where the root is at level 1 — is a level-order query that appears in breadth-first search, layer-by-layer neural network processing, and tree visualization. Key difference from OCaml: 1. **Level vs depth**: The problem uses 1

Tutorial

The Problem

Collecting all nodes at a specific depth (OCaml 99 Problems #33) — where the root is at level 1 — is a level-order query that appears in breadth-first search, layer-by-layer neural network processing, and tree visualization. It is also the key to level-order traversal (BFS on trees).

Level queries are the bridge between depth-first structural recursion (which processes all of a subtree before moving to the next) and breadth-first level-by-level processing. Collecting all nodes at a given level can be done either with DFS (pass the target level as a decreasing counter) or with BFS (queue-based).

🎯 Learning Outcomes

  • • Traverse a tree to a target depth, collecting values only at that level
  • • Use a decreasing level counter: level - 1 at each Node, collect when level == 1
  • • Understand the connection between level-queries and breadth-first traversal
  • • Recognize that collecting all levels produces a level-order traversal
  • • Handle the edge case: level > tree depth returns empty list
  • • Use a decreasing level counter: at_level(tree, level-1) on each child collects nodes one level deeper
  • • Use BFS with a queue as an alternative for collecting all levels in level-order

    • Code Example

    #![allow(clippy::all)]
// Placeholder — pending conversion

    Key Differences

  • Level vs depth: The problem uses 1-based level numbering (root = level 1). Rust's natural 0-based depth (root = depth 0) requires adjustment. Choose a convention and document it.
  • Guard syntax: OCaml's when level = 1 guard in the match arm. Rust: if level == 1 { return ... } or a separate match arm with a guard k if k == 1.
  • **@ efficiency**: OCaml's at_level l (level-1) @ at_level r (level-1) copies the left result. Rust's extend approach is more memory-efficient.
  • BFS alternative: For collecting all levels, BFS with a queue is more efficient (O(n) total) than calling at_level for each level (O(n·d) total).
  • Level counting: "Level 1" is the root (OCaml 99 convention). Rust often uses 0-based levels. Document which convention the function uses to avoid off-by-one bugs.
  • Breadth-first vs depth-first: Collecting all nodes at level d can be done with a depth-first search (decrement d as you descend) or a breadth-first queue (maintain a frontier at each level). Both are O(n).
  • **Vec concatenation:** result.extend(at_level(left, n-1)) is O(k) where k is the number of nodes found. For large trees at deep levels, this allocates frequently — accumulator style is faster.
  • Accumulator for efficiency: Passing &mut Vec<T> as an accumulator parameter avoids O(k) extend overhead per recursive call on deeply nested trees.

    • OCaml Approach

    OCaml's version: let rec at_level tree level = match tree with | Leaf -> [] | Node (x, _, _) when level = 1 -> [x] | Node (_, l, r) -> at_level l (level - 1) @ at_level r (level - 1). The when level = 1 guard returns the value. Otherwise it recurses deeper with decremented level.

    Full Source

    #![allow(clippy::all)]
// Placeholder — pending conversion

    Deep Comparison

    OCaml vs Rust: At Level

    Overview

    See the example.rs and example.ml files for detailed implementations.

    Key Differences

    AspectOCamlRust
    Type systemHindley-MilnerOwnership + traits
    MemoryGCZero-cost abstractions
    MutabilityExplicit refmut keyword
    Error handlingOption/ResultResult<T, E>

    See README.md for detailed comparison.

    Exercises

  • Level-order traversal: Write level_order<T: Clone>(tree: &Tree<T>) -> Vec<Vec<T>> that returns [nodes_at_level_1, nodes_at_level_2, ...] using a queue-based BFS.
  • Maximum sum level: Write max_sum_level(tree: &Tree<i32>) -> usize that returns the level with the highest sum of node values.
  • Zigzag traversal: Write zigzag<T: Clone>(tree: &Tree<T>) -> Vec<Vec<T>> like level-order but alternating left-to-right and right-to-left on each level (a common interview problem).
  • All levels: Implement level_order<T: Clone>(tree: &Tree<T>) -> Vec<Vec<T>> returning all levels as a list of lists, using BFS with a queue.
  • Tree width: Implement width(tree: &Tree<T>) -> usize returning the maximum number of nodes at any single level — the "width" of the tree.

    • Open Source Repos

    functional-rust

    View the source for this example on GitHub — OCaml and Rust side by side in the repo.

    Rust