Tree Traversal Preorder Root Left Right in DSA Rust

Mental Model

Visit the root node first, then explore the left subtree, and finally the right subtree.

Analogy: Imagine reading a family tree starting from the oldest ancestor, then visiting their left child and all descendants, before moving to the right child and their descendants.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Tree: 1 with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in preorder: root first, then left subtree, then right subtree

Step 1: Visit root node 1

Visited: 1

Why: Start traversal at root

Step 2: Traverse left subtree starting at node 2

Visited: 1 -> 2

Why: After root, explore left subtree

Step 3: Traverse left subtree of node 2, visit node 4

Visited: 1 -> 2 -> 4

Why: Preorder visits root of subtree before children

Step 4: Back to node 2, traverse right subtree, visit node 5

Visited: 1 -> 2 -> 4 -> 5

Why: After left child, visit right child

Step 5: Traverse right subtree of root, visit node 3

Visited: 1 -> 2 -> 4 -> 5 -> 3

Why: After left subtree, visit right subtree

Result:

1 -> 2 -> 4 -> 5 -> 3

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
    if let Some(node_rc) = root {
        let node = node_rc.borrow();
        result.push(node.val); // visit root first
        preorder_traversal(node.left.clone(), result); // traverse left subtree
        preorder_traversal(node.right.clone(), result); // traverse right subtree
    }
}

fn main() {
    // Build tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    let root = TreeNode::new(1);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);

    root.borrow_mut().left = Some(node2.clone());
    root.borrow_mut().right = Some(node3.clone());
    node2.borrow_mut().left = Some(node4);
    node2.borrow_mut().right = Some(node5);

    let mut result = Vec::new();
    preorder_traversal(Some(root), &mut result);
    for (i, val) in result.iter().enumerate() {
        if i > 0 {
            print!(" -> ");
        }
        print!("{}", val);
    }
    print!("\n");
}

result.push(node.val); // visit root first

visit current node before children

preorder_traversal(node.left.clone(), result); // traverse left subtree

recursively traverse left subtree

preorder_traversal(node.right.clone(), result); // traverse right subtree

recursively traverse right subtree

Output

1 -> 2 -> 4 -> 5 -> 3

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) due to recursion stack in worst case (skewed tree) and output storage

vs Alternative: Compared to inorder or postorder, preorder visits nodes in a different order but same O(n) time; iterative versions may use explicit stack instead of recursion

Edge Cases

Empty tree (root is None)

No nodes visited, output is empty

DSA Rust

if let Some(node_rc) = root {

Single node tree

Only root node visited and printed

DSA Rust

if let Some(node_rc) = root {

Tree with only left children

Visits nodes top-down left only in preorder

DSA Rust

preorder_traversal(node.left.clone(), result);

When to Use This Pattern

When you need to process the root node before its children in a tree, use preorder traversal because it visits root first, then left, then right.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Ensure the root node is processed (visited) before recursive calls to children

Summary

Visits nodes in order: root, left subtree, then right subtree.

Use when you want to process the root before its children, such as copying a tree or prefix expression evaluation.

The key insight is to visit the current node before recursively visiting its left and right children.

Practice

1. What is the order of nodes visited in a preorder tree traversal?

easy

A. Root, Left, Right

B. Left, Root, Right

C. Left, Right, Root

D. Right, Root, Left

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then the left subtree, and finally the right subtree.

2. Step 2: Match the order with options

   Root, Left, Right matches the order Root, Left, Right exactly.

3. Final Answer:

   Root, Left, Right -> Option A

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember preorder starts with the root node first [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Swapping left and right subtree order
• Thinking traversal starts with left child

2. Which Rust code snippet correctly implements preorder traversal for a binary tree node Node with left and right children?

easy

A. fn preorder(node: &Option) { if let Some(n) = node { print!("{} ", n.value); preorder(&n.left); preorder(&n.right); } }

B. fn preorder(node: &Option) { if let Some(n) = node { preorder(&n.left); print!("{} ", n.value); preorder(&n.right); } }

C. fn preorder(node: &Option) { if let Some(n) = node { preorder(&n.left); preorder(&n.right); print!("{} ", n.value); } }

D. fn preorder(node: &Option) { if let Some(n) = node { preorder(&n.right); print!("{} ", n.value); preorder(&n.left); } }

Solution

1. Step 1: Identify preorder traversal steps in code

   Preorder visits root first (print value), then left subtree, then right subtree.

2. Step 2: Check each option's order

   fn preorder(node: &Option) { if let Some(n) = node { print!("{} ", n.value); preorder(&n.left); preorder(&n.right); } } prints root value first, then recursively visits left and right children, matching preorder.

3. Final Answer:

   Print root value first, then left, then right -> Option A

4. Quick Check:

   Print root before children = preorder [OK]

Hint: Print root value before recursive calls for preorder [OK]

Common Mistakes:

• Printing after left subtree (inorder)
• Printing after both subtrees (postorder)
• Swapping left and right recursive calls

3. Given the binary tree below, what is the preorder traversal output?

    10
   /  \
  5    15
 /    /  \
3    12  20

medium

A. [10, 15, 20, 12, 5, 3]

B. [3, 5, 10, 12, 15, 20]

C. [5, 3, 10, 12, 15, 20]

D. [10, 5, 3, 15, 12, 20]

Solution

1. Step 1: Start at root and visit nodes in preorder

   Visit root 10, then left subtree: 5, then 3. Then right subtree: 15, then 12, then 20.

2. Step 2: Write traversal sequence

   Sequence is 10, 5, 3, 15, 12, 20 matching [10, 5, 3, 15, 12, 20].

3. Final Answer:

   [10, 5, 3, 15, 12, 20] -> Option D

4. Quick Check:

   Preorder visits root first, then left, then right [OK]

Hint: Follow root-left-right order step by step [OK]

Common Mistakes:

• Listing nodes in inorder or postorder
• Mixing left and right subtree order
• Skipping leaf nodes

4. The following Rust function is intended to perform preorder traversal but has a bug. What is the bug?

fn preorder(node: &Option) {
    if let Some(n) = node {
        preorder(&n.left);
        print!("{} ", n.value);
        preorder(&n.right);
    }
}

medium

A. It visits the right subtree before the left subtree.

B. It does not check if the node is None before recursion.

C. It prints the root value after visiting the left subtree, so it is inorder traversal.

D. It does not print the root value at all.

Solution

1. Step 1: Analyze order of operations in function

   The function calls preorder on left child first, then prints root value, then calls preorder on right child.

2. Step 2: Identify traversal type from order

   This order is Left, Root, Right which is inorder traversal, not preorder.

3. Final Answer:

   Print happens after left subtree, so it's inorder traversal -> Option C

4. Quick Check:

   Preorder prints root first, this prints after left [OK]

Hint: Print root before recursive calls for preorder [OK]

Common Mistakes:

• Confusing preorder with inorder traversal
• Ignoring order of print statement
• Assuming recursion order alone defines traversal

5. You want to collect all node values in preorder traversal into a vector in Rust. Which code snippet correctly does this?

hard

A. fn preorder_collect(node: &Option, vals: &mut Vec<i32>) { if let Some(n) = node { preorder_collect(&n.left, vals); vals.push(n.value); preorder_collect(&n.right, vals); } }

B. fn preorder_collect(node: &Option, vals: &mut Vec<i32>) { if let Some(n) = node { vals.push(n.value); preorder_collect(&n.left, vals); preorder_collect(&n.right, vals); } }

C. fn preorder_collect(node: &Option, vals: &mut Vec<i32>) { if let Some(n) = node { preorder_collect(&n.left, vals); preorder_collect(&n.right, vals); vals.push(n.value); } }

D. fn preorder_collect(node: &Option, vals: &mut Vec<i32>) { if let Some(n) = node { preorder_collect(&n.right, vals); vals.push(n.value); preorder_collect(&n.left, vals); } }

Solution

1. Step 1: Understand preorder collection order

   Preorder means add root value first, then collect left subtree, then right subtree.

2. Step 2: Check which code pushes root value first

   fn preorder_collect(node: &Option, vals: &mut Vec<i32>) { if let Some(n) = node { vals.push(n.value); preorder_collect(&n.left, vals); preorder_collect(&n.right, vals); } } pushes root value before recursive calls, matching preorder.

3. Final Answer:

   Push root value first, then left, then right -> Option B

4. Quick Check:

   Push root before children for preorder collection [OK]

Hint: Push root value before recursive calls to collect preorder [OK]

Common Mistakes:

• Pushing after left subtree (inorder)
• Pushing after both subtrees (postorder)
• Swapping left and right recursion order