Tree Traversal Preorder Root Left Right in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Preorder Traversal on a Simple Binary Tree

What is the output of the preorder traversal (Root, Left, Right) of the following binary tree?

Tree structure:
1
/ \ 2 3
/
4

DSA Rust

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

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

fn main() {
    let root = Some(Box::new(Node {
        val: 1,
        left: Some(Box::new(Node {
            val: 2,
            left: Some(Box::new(Node { val: 4, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(Node { val: 3, left: None, right: None })),
    }));
    let mut result = Vec::new();
    preorder(&root, &mut result);
    println!("{:?}", result);
}

A [1, 2, 4, 3]

B [1, 3, 2, 4]

C [2, 4, 1, 3]

D [4, 2, 1, 3]

💡 Hint

Remember preorder traversal visits the root node first, then left subtree, then right subtree.

Preorder traversal visits nodes in the order: root, left child, then right child. So starting at 1, then left subtree 2 and its left child 4, then right subtree 3.

❓ Predict Output

intermediate

Preorder Traversal Output with Missing Right Child

What is the preorder traversal output of this binary tree?

Tree structure:
5
/ \ 6 null
/ \ 7 8

DSA Rust

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

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

fn main() {
    let root = Some(Box::new(Node {
        val: 5,
        left: Some(Box::new(Node {
            val: 6,
            left: Some(Box::new(Node { val: 7, left: None, right: None })),
            right: Some(Box::new(Node { val: 8, left: None, right: None })),
        })),
        right: None,
    }));
    let mut result = Vec::new();
    preorder(&root, &mut result);
    println!("{:?}", result);
}

A [5, 6, 8, 7]

B [5, 6, 7, 8]

C [6, 7, 8, 5]

D [7, 6, 8, 5]

💡 Hint

Preorder visits root first, then left subtree, then right subtree. Right child of root is missing here.

Start at root 5, then left subtree 6, then 6's left child 7, then 6's right child 8. No right child of 5 to visit.

🔧 Debug

advanced

Identify the Error in Preorder Traversal Implementation

What error will this Rust code produce when running preorder traversal on a binary tree?

DSA Rust

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

fn preorder(root: &Option<Box<Node>>, result: &mut Vec<i32>) {
    if root.is_some() {
        let node = root.as_ref().unwrap();
        result.push(node.val);
        preorder(&node.left, result);
        preorder(&node.right, result);
    }
}

fn main() {
    let root = Some(Box::new(Node {
        val: 10,
        left: None,
        right: None,
    }));
    let mut result = Vec::new();
    preorder(&root, &mut result);
    println!("{:?}", result);
}

A Compilation error: cannot move out of borrowed content

B panic at 'called `Option::unwrap()` on a None value'

C [10]

D Empty output []

💡 Hint

Check how unwrap() is used on a reference to Option>.

Calling unwrap() on a reference to Option> tries to move the Box out, which is not allowed. This causes a compilation error about moving out of borrowed content.

❓ Predict Output

advanced

Preorder Traversal Output of a Larger Tree

What is the preorder traversal output of this binary tree?

Tree structure:
10
/ \ > 5 15
/ \ \ > 3 7 20

DSA Rust

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

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

fn main() {
    let root = Some(Box::new(Node {
        val: 10,
        left: Some(Box::new(Node {
            val: 5,
            left: Some(Box::new(Node { val: 3, left: None, right: None })),
            right: Some(Box::new(Node { val: 7, left: None, right: None })),
        })),
        right: Some(Box::new(Node {
            val: 15,
            left: None,
            right: Some(Box::new(Node { val: 20, left: None, right: None })),
        })),
    }));
    let mut result = Vec::new();
    preorder(&root, &mut result);
    println!("{:?}", result);
}

A [10, 5, 7, 3, 15, 20]

B [10, 15, 20, 5, 3, 7]

C [3, 5, 7, 10, 15, 20]

D [10, 5, 3, 7, 15, 20]

💡 Hint

Preorder visits root, then left subtree, then right subtree recursively.

Start at root 10, then left subtree 5, then 5's left 3, 5's right 7, then right subtree 15, then 15's right 20.

🧠 Conceptual

expert

Number of Nodes Visited in Preorder Traversal

Given a binary tree with 7 nodes, how many nodes does the preorder traversal visit?

A 8

B 6

C 7

D Depends on tree shape

💡 Hint

Preorder traversal visits every node exactly once.

Preorder traversal visits every node in the tree exactly once, so for 7 nodes, it visits 7 nodes.

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