Tree Traversal Preorder Root Left Right in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to print the root node's value first in preorder traversal.

DSA Rust

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(ref n) = *node {
        println!("{}", [1]);
    }
}

Drag options to blanks, or click blank then click option'

Anode.left

Bnode.val

Cn.left

Dn.val

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to print 'node.val' which is an Option and does not have 'val' directly.

Printing left or right child instead of the root node's value.

In preorder traversal, we first visit the root node's value. Here, 'n' is the current node, so we print 'n.val'.

2fill in blank

medium

Complete the code to recursively traverse the left subtree in preorder.

DSA Rust

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(ref n) = *node {
        println!("{}", n.val);
        preorder(&[1]);
    }
}

Drag options to blanks, or click blank then click option'

An.left

Bnode.left

Cn.right

Dnode.right

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node.left' which is an Option reference, but 'node' is already an Option.

Calling preorder on the right child instead of the left.

After visiting the root, preorder traversal visits the left subtree. The left child is 'n.left'.

3fill in blank

hard

Fix the error in the code to correctly traverse the right subtree after the left subtree in preorder.

DSA Rust

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(ref n) = *node {
        println!("{}", n.val);
        preorder(&n.left);
        preorder(&[1]);
    }
}

Drag options to blanks, or click blank then click option'

Anode.right

Bn.left

Cn.right

Dnode.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node.right' which is an Option reference, but 'node' is already an Option.

Repeating 'n.left' instead of using 'n.right'.

After traversing the left subtree, preorder traversal visits the right subtree. The right child is 'n.right'.

4fill in blank

hard

Fill both blanks to complete the preorder traversal function that prints root, then left, then right.

DSA Rust

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(ref n) = *node {
        println!("{}", [1]);
        preorder(&[2]);
        preorder(&n.right);
    }
}

Drag options to blanks, or click blank then click option'

An.val

Bnode.val

Cn.left

Dnode.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node.val' or 'node.left' which are not directly accessible.

Swapping left and right subtree calls.

We print the root value 'n.val', then recursively traverse the left subtree 'n.left', and finally the right subtree.

5fill in blank

hard

Fill all three blanks to complete the preorder traversal that prints root, then left, then right subtree recursively.

DSA Rust

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(ref n) = *node {
        println!("{}", [1]);
        preorder(&[2]);
        preorder(&[3]);
    }
}

Drag options to blanks, or click blank then click option'

An.val

Bn.left

Cn.right

Dnode.val

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node.val' instead of 'n.val'.

Mixing up left and right subtree references.

Preorder traversal visits root 'n.val', then left subtree 'n.left', then right subtree 'n.right'.

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