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.

Basic Implementation

basic.rs

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));
}

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].

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