032 Intermediate GitHub

032 — Collect the Internal Nodes of a Binary Tree

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "032 — Collect the Internal Nodes of a Binary Tree" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Internal nodes (non-leaf nodes) of a binary tree (OCaml 99 Problems #32) are those with at least one child that is not a `Leaf`. Key difference from OCaml: 1. **Exhaustive matching**: Rust's `match` must cover all cases. You cannot forget the `Node(_, Leaf, Leaf)` case — omitting it is a compile error. OCaml's match is also exhaustive by default.

Tutorial

The Problem

Internal nodes (non-leaf nodes) of a binary tree (OCaml 99 Problems #32) are those with at least one child that is not a Leaf. Collecting internal nodes is the complement of collecting leaves — together they enumerate all nodes in the tree. In a binary search tree, internal nodes are where routing decisions are made; in a parse tree, they represent grammatical rules rather than terminals.

This problem reinforces the pattern of filtering nodes by structural property during traversal. The structural condition — has at least one non-leaf child — is expressed naturally through pattern matching, without explicit null checks.

🎯 Learning Outcomes

• Distinguish internal nodes from leaves using pattern matching on tree structure

• Collect internal node values using recursive left-right traversal

• Understand the structural predicate: a node is internal if either child is a Node

• Recognize that count_internal + count_leaves = count_nodes (by definition)

• Apply the collect-and-filter pattern to tree traversal

• Match Tree::Node(v, _, _) where at least one child is not Leaf to identify internal nodes

• Verify the complementary relationship: leaves + internal_nodes = total_nodes in property tests

Code Example

#![allow(clippy::all)]
// Collect internal node values (any node that is not Node(x, Leaf, Leaf)), preorder (OCaml 99 Problems #32).
#[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 collect_internal<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(_, l, r) if matches!(**l, Tree::Leaf) && matches!(**r, Tree::Leaf) => vec![],
        Tree::Node(v, l, r) => {
            let mut result = vec![v.clone()];
            result.extend(collect_internal(l));
            result.extend(collect_internal(r));
            result
        }
    }
}

#[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_collect_internal_preorder() {
        assert_eq!(collect_internal(&sample()), vec![1, 3]);
    }

    #[test]
    fn test_single_node_has_no_internal() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_internal(&Tree::node(9, Tree::leaf(), Tree::leaf())), empty);
    }

    #[test]
    fn test_empty_tree_has_no_internal() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_internal::<i32>(&Tree::leaf()), empty);
    }
}

(* Internal Nodes *)
(* OCaml 99 Problems #32 *)

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 collect_internal = function
  | Leaf -> []
  | Node (_, Leaf, Leaf) -> []
  | Node (x, l, r) -> x :: collect_internal l @ collect_internal r

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

Key Differences

Exhaustive matching: Rust's match must cover all cases. You cannot forget the Node(_, Leaf, Leaf) case — omitting it is a compile error. OCaml's match is also exhaustive by default.

Pattern nesting: Matching on Tree::Node(v, Tree::Leaf, Tree::Leaf) vs Tree::Node(v, _, _) requires nested patterns. Both languages support this naturally.

Value borrowing: Rust's v in Tree::Node(v, l, r) borrows the value by reference. To collect owned copies, the bound must be T: Clone and you must call .clone().

Performance: Collecting into a Vec with recursive extend is O(n). OCaml's @ inside the recursive call can make this O(n·d) in the worst case if not using an accumulator.

Structural predicate: "Is internal" = "has at least one non-Leaf child". This is expressed as a pattern: Node(_, _, _) where at least one branch is not Leaf. Rust and OCaml use identical structural patterns.

Complement of leaves: collect_internal + collect_leaves = all node values. This invariant can be verified in tests.

Traversal order: Both implementations collect internal nodes in pre-order (root before children). Post-order or in-order collection is equally valid — the order depends on the use case.

Efficiency: Using an accumulator avoids the O(n·d) cost of extend on deep trees. Pass a &mut Vec<T> instead of returning a Vec<T> for the most efficient form.

OCaml Approach

OCaml's version: let rec internals = function | Leaf -> [] | Node (_, Leaf, Leaf) -> [] | Node (x, l, r) -> x :: internals l @ internals r. The second case explicitly excludes nodes with two leaf children. The third case collects the value and recurses. Like leaves, use accumulator style for efficiency: x :: internals l @ internals r is O(|left|) for the @.

Full Source

#![allow(clippy::all)]
// Collect internal node values (any node that is not Node(x, Leaf, Leaf)), preorder (OCaml 99 Problems #32).
#[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 collect_internal<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(_, l, r) if matches!(**l, Tree::Leaf) && matches!(**r, Tree::Leaf) => vec![],
        Tree::Node(v, l, r) => {
            let mut result = vec![v.clone()];
            result.extend(collect_internal(l));
            result.extend(collect_internal(r));
            result
        }
    }
}

#[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_collect_internal_preorder() {
        assert_eq!(collect_internal(&sample()), vec![1, 3]);
    }

    #[test]
    fn test_single_node_has_no_internal() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_internal(&Tree::node(9, Tree::leaf(), Tree::leaf())), empty);
    }

    #[test]
    fn test_empty_tree_has_no_internal() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_internal::<i32>(&Tree::leaf()), empty);
    }
}

(* Internal Nodes *)
(* OCaml 99 Problems #32 *)

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 collect_internal = function
  | Leaf -> []
  | Node (_, Leaf, Leaf) -> []
  | Node (x, l, r) -> x :: collect_internal l @ collect_internal r

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (collect_internal sample = [1; 3]);
  assert (collect_internal (node 9 leaf leaf) = []);
  assert (collect_internal leaf = []);
  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_collect_internal_preorder() {
        assert_eq!(collect_internal(&sample()), vec![1, 3]);
    }

    #[test]
    fn test_single_node_has_no_internal() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_internal(&Tree::node(9, Tree::leaf(), Tree::leaf())), empty);
    }

    #[test]
    fn test_empty_tree_has_no_internal() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_internal::<i32>(&Tree::leaf()), empty);
    }
}

Deep Comparison

OCaml vs Rust: Internal Nodes

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

One-child nodes: Write one_child_nodes<T: Clone>(tree: &Tree<T>) -> Vec<T> that collects nodes where exactly one child is a non-Leaf. Match on Node(v, Leaf, Node(...)) and Node(v, Node(...), Leaf).

Partition tree: Write partition_tree<T: Clone>(tree: &Tree<T>) -> (Vec<T>, Vec<T>) that returns (internal_nodes, leaf_node_values) in a single traversal.

Tree statistics: Write tree_stats<T>(tree: &Tree<T>) -> (usize, usize, usize) returning (leaves, internal, total) in one pass without making multiple calls.

Internal node predicate: Write is_internal<T>(tree: &Tree<T>) -> bool that returns true if the root node has at least one non-Leaf child — the core condition used in collect_internal.

Internal node count: Implement count_internal<T>(tree: &Tree<T>) -> usize and verify that count_internal + count_leaves == count_nodes in property tests using generated trees.

Open Source Repos

functional-rust

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

Rust