Tree Traversals

Tree traversal refers to the process of visiting every node in a tree exactly once in a systematic way. Because trees are non-linear, there are multiple valid traversal strategies, each useful for different types of problems.

Traversal algorithms are typically categorized as depth-first or breadth-first.

Depth-First Traversals (DFS)

Depth-first traversals explore as far down a branch as possible before backtracking.

There are three common DFS traversal orders for binary trees:

1. In-order
2. Pre-order
3. Post-order

These differ only in when the current node is visited.

In-order Traversal (Left → Root → Right)

In-order traversal visits the left subtree, then the current node, and finally the right subtree.

        1
       / \
      2   3
     / \
    4   5

Traversal result:

[4, 2, 5, 1, 3]

Use cases

• Produces sorted output for binary search trees
• Expression tree evaluation (infix notation)

Pre-order Traversal (Root → Left → Right)

Pre-order traversal visits the current node before its children.

Traversal result:

[1, 2, 4, 5, 3]

Use cases

• Tree serialization
• Copying or cloning trees
• Prefix notation expressions

Post-order Traversal (Left → Right → Root)

Post-order traversal visits children before the parent node.

Traversal result:

[4, 5, 2, 3, 1]

Use cases

• Deleting/freeing trees
• Postfix expression evaluation

Breadth-First Traversal (Level-order)

Breadth-first traversal visits nodes level by level from top to bottom, left to right.

Traversal result:

[1, 2, 3, 4, 5]

This traversal uses a queue internally and is also known as level-order traversal.

Rust Implementation

Below are recursive implementations of the three DFS traversals, followed by an iterative BFS traversal.

use std::collections::VecDeque;

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}

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

// In-order traversal
pub fn inorder<T: Clone>(node: &Option<Box<Node<T>>>, result: &mut Vec<T>) {
    if let Some(n) = node {
        inorder(&n.left, result);
        result.push(n.value.clone());
        inorder(&n.right, result);
    }
}

// Pre-order traversal
pub fn preorder<T: Clone>(node: &Option<Box<Node<T>>>, result: &mut Vec<T>) {
    if let Some(n) = node {
        result.push(n.value.clone());
        preorder(&n.left, result);
        preorder(&n.right, result);
    }
}

// Post-order traversal
pub fn postorder<T: Clone>(node: &Option<Box<Node<T>>>, result: &mut Vec<T>) {
    if let Some(n) = node {
        postorder(&n.left, result);
        postorder(&n.right, result);
        result.push(n.value.clone());
    }
}

// Level-order traversal (BFS)
pub fn level_order<T: Clone>(root: &Option<Box<Node<T>>>) -> Vec<T> {
    let mut result = Vec::new();
    let mut queue = VecDeque::new();

    if let Some(node) = root {
        queue.push_back(node);
    }

    while let Some(node) = queue.pop_front() {
        result.push(node.value.clone());

        if let Some(ref left) = node.left {
            queue.push_back(left);
        }

        if let Some(ref right) = node.right {
            queue.push_back(right);
        }
    }

    result
}

Example Usage

fn main() {
    let mut root = Node::new(1);

    root.left = Some(Box::new(Node::new(2)));
    root.right = Some(Box::new(Node::new(3)));

    if let Some(ref mut left) = root.left {
        left.left = Some(Box::new(Node::new(4)));
        left.right = Some(Box::new(Node::new(5)));
    }

    let root = Some(Box::new(root));

    let mut inorder_result = Vec::new();
    inorder(&root, &mut inorder_result);

    let mut preorder_result = Vec::new();
    preorder(&root, &mut preorder_result);

    let mut postorder_result = Vec::new();
    postorder(&root, &mut postorder_result);

    let level_order_result = level_order(&root);

    println!("In-order: {:?}", inorder_result);
    println!("Pre-order: {:?}", preorder_result);
    println!("Post-order: {:?}", postorder_result);
    println!("Level-order: {:?}", level_order_result);
}

Time and Space Complexity

All traversal methods visit each node exactly once.

Time Complexity

Space Complexity

Playground Links

Rust - Tree Traversals