033 Intermediate GitHub

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)]
// Collect node values at a given 1-based level (root = level 1) (OCaml 99 Problems #33).
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }
}

pub fn at_level<T: Clone>(tree: &Tree<T>, level: usize) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(v, _, _) if level == 1 => vec![v.clone()],
        Tree::Node(_, l, r) if level > 1 => {
            let mut result = at_level(l, level - 1);
            result.extend(at_level(r, level - 1));
            result
        }
        Tree::Node(_, _, _) => vec![], // level == 0: no 0-th level in a 1-based scheme
    }
}

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

    fn sample() -> Tree<i32> {
        Tree::node(
            1,
            Tree::node(2, Tree::leaf(), Tree::leaf()),
            Tree::node(3, Tree::node(4, Tree::leaf(), Tree::leaf()), Tree::leaf()),
        )
    }

    #[test]
    fn test_level_1_is_root() {
        assert_eq!(at_level(&sample(), 1), vec![1]);
    }

    #[test]
    fn test_level_2_is_roots_children() {
        assert_eq!(at_level(&sample(), 2), vec![2, 3]);
    }

    #[test]
    fn test_level_3() {
        assert_eq!(at_level(&sample(), 3), vec![4]);
    }

    #[test]
    fn test_level_beyond_depth_is_empty() {
        let empty: Vec<i32> = vec![];
        assert_eq!(at_level(&sample(), 4), empty);
    }
}

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

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

let node x l r = Node (x, l, r)
let leaf = Leaf

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)

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (at_level sample 1 = [1]);
  assert (at_level sample 2 = [2; 3]);
  assert (at_level sample 3 = [4]);
  assert (at_level sample 4 = []);
  print_endline "✓ OCaml tests passed"

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)]
// Collect node values at a given 1-based level (root = level 1) (OCaml 99 Problems #33).
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }
}

pub fn at_level<T: Clone>(tree: &Tree<T>, level: usize) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(v, _, _) if level == 1 => vec![v.clone()],
        Tree::Node(_, l, r) if level > 1 => {
            let mut result = at_level(l, level - 1);
            result.extend(at_level(r, level - 1));
            result
        }
        Tree::Node(_, _, _) => vec![], // level == 0: no 0-th level in a 1-based scheme
    }
}

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

    fn sample() -> Tree<i32> {
        Tree::node(
            1,
            Tree::node(2, Tree::leaf(), Tree::leaf()),
            Tree::node(3, Tree::node(4, Tree::leaf(), Tree::leaf()), Tree::leaf()),
        )
    }

    #[test]
    fn test_level_1_is_root() {
        assert_eq!(at_level(&sample(), 1), vec![1]);
    }

    #[test]
    fn test_level_2_is_roots_children() {
        assert_eq!(at_level(&sample(), 2), vec![2, 3]);
    }

    #[test]
    fn test_level_3() {
        assert_eq!(at_level(&sample(), 3), vec![4]);
    }

    #[test]
    fn test_level_beyond_depth_is_empty() {
        let empty: Vec<i32> = vec![];
        assert_eq!(at_level(&sample(), 4), empty);
    }
}

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

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

let node x l r = Node (x, l, r)
let leaf = Leaf

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)

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (at_level sample 1 = [1]);
  assert (at_level sample 2 = [2; 3]);
  assert (at_level sample 3 = [4]);
  assert (at_level sample 4 = []);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    fn sample() -> Tree<i32> {
        Tree::node(
            1,
            Tree::node(2, Tree::leaf(), Tree::leaf()),
            Tree::node(3, Tree::node(4, Tree::leaf(), Tree::leaf()), Tree::leaf()),
        )
    }

    #[test]
    fn test_level_1_is_root() {
        assert_eq!(at_level(&sample(), 1), vec![1]);
    }

    #[test]
    fn test_level_2_is_roots_children() {
        assert_eq!(at_level(&sample(), 2), vec![2, 3]);
    }

    #[test]
    fn test_level_3() {
        assert_eq!(at_level(&sample(), 3), vec![4]);
    }

    #[test]
    fn test_level_beyond_depth_is_empty() {
        let empty: Vec<i32> = vec![];
        assert_eq!(at_level(&sample(), 4), empty);
    }
}

Deep Comparison

OCaml vs Rust: At Level

Overview

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

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<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