Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Rust DSA implementation can be compared directly with the rest of the DSA track.

preorder Preorder records the current node before visiting left and right subtrees.

Basic Implementation

basic.rs
Replay: real traced execution (multi-file project)
use std::collections::VecDeque;

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(value: i32) -> Self {
        Self { value, left: None, right: None }
    }

    fn with(value: i32, left: Node, right: Node) -> Self {
        Self {
            value,
            left: Some(Box::new(left)),
            right: Some(Box::new(right)),
        }
    }
}

fn render(node: &Option<Box<Node>>) -> String {
    match node {
        None => "_".to_string(),
        Some(n) => {
            if n.left.is_none() && n.right.is_none() {
                n.value.to_string()
            } else {
                format!("{}({},{})", n.value, render(&n.left), render(&n.right))
            }
        }
    }
}

fn sample_tree() -> Option<Box<Node>> {
    Some(Box::new(Node::with(
        4,
        Node::with(2, Node::new(1), Node::new(3)),
        Node::with(6, Node::new(5), Node::new(7)),
    )))
}

fn list_string(values: &[i32]) -> String {
    format!(
        "[{}]",
        values
            .iter()
            .map(|v| v.to_string())
            .collect::<Vec<_>>()
            .join(", ")
    )
}

fn preorder(node: &Option<Box<Node>>, output: &mut Vec<i32>) {
    if let Some(n) = node {
        output.push(n.value);
        preorder(&n.left, output);
        preorder(&n.right, output);
    }
}

fn main() {
    let root = sample_tree();
    let mut output = Vec::new();
    preorder(&root, &mut output);
    println!("{}", list_string(&output));
}

  1. tree ← 4(2(1,3),6(5,7)), output ← []

    36fn sample_tree() -> Option<Box<Node>> {37    Some(Box::new(Node::with(
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[] → [4]output4node

  3. output ← [4, 2]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[4, 2] → [4, 2, 1]output1node

  5. output ← [4, 2, 1, 3]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

  6. output ← [4, 2, 1, 3, 6]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

  7. output ← [4, 2, 1, 3, 6, 5]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

  8. output ← [4, 2, 1, 3, 6, 5, 7]

    56if let Some(n) = node {57    output.push(n.value);58    preorder(&n.left, output);
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. println!("{}", list_string(&output));

    66    preorder(&root, &mut output);67    println!("{}", list_string(&output));68}
    values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

Implementation notes

  • Rust stores each tree node as Node { value: i32, left: Option<Box<Node>>, right: Option<Box<Node>> }, so child links own boxed subtrees and None marks an empty child.
  • preorder(node: &Option<Box<Node>>, output: &mut Vec<i32>) borrows the tree and mutates only the output vector; recursive calls pass &n.left and &n.right rather than moving child boxes.
  • if let Some(n) = node skips None children. For real nodes, n.value is copied into output before the left and right recursive calls.
  • The checked source imports VecDeque, but this traversal does not use a queue; the traversal state is the Rust call stack plus output: Vec<i32>.
  • The trace records visit-before-children states in this order: 4, 2, 1, 3, 6, 5, 7, with output growing from [] to [4, 2, 1, 3, 6, 5, 7].
  • list_string(&output) borrows the result slice, joins display-formatted integers, and println!("{}", ...) prints [4, 2, 1, 3, 6, 5, 7].