🎬 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

032: Internal Nodes

Difficulty: ⭐ Level: Foundations Collect the values of all internal nodes — nodes that have at least one child.

The Problem This Solves

Internal nodes are the decision points in a tree. In a decision tree, they're the questions ("Is it an animal?"). In a file system, they're the directories. In a syntax tree, they're the operators and keywords — the structure, not the data. Splitting a tree into "leaves" (example 031) and "internal nodes" (this example) lets you analyze the two parts separately. How many decisions vs outcomes? How much structure vs how much data? This decomposition shows up in compression, AI, and compiler design.

The Intuition

The definition of an internal node is the opposite of a leaf: a node is internal if at least one of its children is not `Leaf`. In our tree, a `Node(Leaf, v, Leaf)` is a leaf node — no real children. A `Node(something, v, Leaf)` or `Node(Leaf, v, something)` is internal — at least one real subtree. In Python:

def is_internal(node):
 return node.left is not None or node.right is not None

In Rust, we flip the leaf pattern — match `(Leaf, Leaf)` to skip, everything else is internal:

match (l.as_ref(), r.as_ref()) {
 (Tree::Leaf, Tree::Leaf) => vec![],  // leaf node — skip it
 _ => { /* this is internal — collect it */ }
}

The ordering in the result (left internals, then current node, then right internals) is in-order — internal nodes are visited in left-root-right order.

How It Works in Rust

fn internals<T: Clone>(tree: &Tree<T>) -> Vec<T> {
 match tree {
     Tree::Leaf => vec![],  // empty tree → nothing

     Tree::Node(l, v, r) => match (l.as_ref(), r.as_ref()) {
         // Both children are empty → leaf node, not internal
         (Tree::Leaf, Tree::Leaf) => vec![],

         // At least one real child → this is an internal node
         _ => {
             let mut result = internals(l);  // left subtree internals
             result.push(v.clone());          // this node
             result.extend(internals(r));     // right subtree internals
             result
         }
     },
 }
}

For this tree:

    a         ← internal (has children b, c)
   / \
  b   c       ← b is internal; c has no children → leaf
 / \
d   e         ← d, e are leaves

`internals(&t)` returns `['b', 'a']` — in-order.

What This Unlocks

Tree analysis: ratio of internal/leaf nodes measures branching factor.
Compiler passes: internal nodes are the operations; traversing them applies transformations.
Decision trees in ML: internal nodes are the split conditions you'd extract for interpretation.

Key Differences

Concept	OCaml	Rust
Negating a leaf pattern	`match (l,r) with (Leaf,Leaf) -> []`	Same — match the case to skip, `_` catches the rest
In-order collection	`(internals l) @ [v] @ (internals r)`	`result` Vec: push left, push v, extend right
Wildcard pattern	`_`	`_` — same syntax

// Internal Nodes — 99 Problems #32
// Collect the internal nodes of a binary tree.
// An internal node has at least one non-Leaf child.

#[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 internals<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(l, v, r) => match (l.as_ref(), r.as_ref()) {
            // Both children are Leaf → this is a leaf node, not internal
            (Tree::Leaf, Tree::Leaf) => vec![],
            _ => {
                // This node is internal
                let mut result = internals(l);
                result.push(v.clone());
                result.extend(internals(r));
                result
            }
        },
    }
}

fn sample_tree() -> Tree<char> {
    //        a         ← internal (has children b, c)
    //       / \
    //      b   c      ← b is internal; c is leaf
    //     / \
    //    d   e        ← d, e are leaves
    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!("Internal nodes: {:?}", internals(&t));  // [b, a] or similar in-order

    let single = Tree::node(Tree::leaf(), 'z', Tree::leaf());
    println!("Single node internals: {:?}", internals(&single)); // []

    let chain = Tree::node(
        Tree::leaf(),
        1,
        Tree::node(Tree::leaf(), 2, Tree::node(Tree::leaf(), 3, Tree::leaf())),
    );
    println!("Chain internals: {:?}", internals(&chain)); // [1, 2]
}

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

    #[test]
    fn test_empty() {
        let t: Tree<i32> = Tree::leaf();
        assert_eq!(internals(&t), vec![]);
    }

    #[test]
    fn test_single_node_is_not_internal() {
        let t = Tree::node(Tree::leaf(), 42, Tree::leaf());
        assert_eq!(internals(&t), vec![]);
    }

    #[test]
    fn test_sample_tree() {
        // b and a are internal; c, d, e are leaves
        let result = internals(&sample_tree());
        assert!(result.contains(&'a'));
        assert!(result.contains(&'b'));
        assert!(!result.contains(&'c'));
        assert_eq!(result.len(), 2);
    }

    #[test]
    fn test_chain() {
        let chain = Tree::node(
            Tree::leaf(),
            1,
            Tree::node(Tree::leaf(), 2, Tree::node(Tree::leaf(), 3, Tree::leaf())),
        );
        assert_eq!(internals(&chain), vec![1, 2]);
    }
}

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

(* Implementation for example 32 *)

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