Tree Traversal Preorder Root Left Right in DSA Rust - Execution Trace

Concept Flow - Tree Traversal Preorder Root Left Right

Start at Root Node

↓

Visit Node (Process Data)

↓

Traverse Left Subtree

↓

Traverse Right Subtree

↓

Done

Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree.

Execution Sample

DSA Rust

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(n) = node {
        print!("{} ", n.val);
        preorder(&n.left);
        preorder(&n.right);
    }
}

This function prints nodes in preorder: root, left subtree, then right subtree.

Execution Table

Step	Operation	Node Visited	Left/Right	Tree State
1	Visit root	1	root	1 / \ 2 3
2	Traverse left subtree	2	left	1 / \ 2 3
3	Visit node	2	left	1 / \ 2 3
4	Traverse left subtree	4	left of 2	1 / \ 2 3 / 4
5	Visit node	4	left of 2	1 / \ 2 3 / 4
6	Traverse left subtree	None	left of 4	1 / \ 2 3 / 4
7	Traverse right subtree	None	right of 4	1 / \ 2 3 / 4
8	Traverse right subtree	5	right of 2	1 / \ 2 3 / \ 4 5
9	Visit node	5	right of 2	1 / \ 2 3 / \ 4 5
10	Traverse left subtree	None	left of 5	1 / \ 2 3 / \ 4 5
11	Traverse right subtree	None	right of 5	1 / \ 2 3 / \ 4 5
12	Traverse right subtree	3	right	1 / \ 2 3 / \ 4 5
13	Visit node	3	right	1 / \ 2 3 / \ 4 5
14	Traverse left subtree	None	left of 3	1 / \ 2 3 / \ 4 5
15	Traverse right subtree	None	right of 3	1 / \ 2 3 / \ 4 5
16	Done	None	none	Traversal complete: 1 2 4 5 3

💡 All nodes visited in preorder: root, left subtree, right subtree.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 9	After Step 13	Final
Current Node	1 (root)	1	2	4	5	3	None
Visited Nodes	[]	[1]	[1,2]	[1,2,4]	[1,2,4,5]	[1,2,4,5,3]	[1,2,4,5,3]

Key Moments - 3 Insights

Why do we visit the root node before its children?

Because preorder traversal's rule is to process the root first, then left subtree, then right subtree, as shown in steps 1, 3, 5, and 9 in the execution_table.

What happens when a node has no left or right child?

The traversal calls preorder on None, which immediately returns without action, as seen in steps 6, 7, 10, 11, 14, and 15 where no nodes are visited.

How do we know when traversal is complete?

When all nodes have been visited and recursive calls return, shown at step 16 with the final traversal order.

Visual Quiz - 3 Questions

Look at the execution_table, what node is visited at step 9?

A Node 5

B Node 4

C Node 3

D Node 2

💡 Hint

Refer to the 'Node Visited' column at step 9 in the execution_table.

At which step does the traversal visit the right subtree of the root node?

A Step 8

B Step 3

C Step 12

D Step 5

💡 Hint

Check the 'Operation' and 'Left/Right' columns for the root's right subtree traversal.

If the left child of node 2 was missing, how would the traversal order change?

A Node 3 would be visited earlier

B Node 4 would be skipped, traversal order: 1 2 5 3

C Node 5 would be skipped, traversal order: 1 2 4 3

D Traversal order would remain the same

💡 Hint

Refer to the variable_tracker and execution_table steps involving node 4.

Concept Snapshot

Preorder traversal visits nodes in this order:
1. Root node first
2. Then left subtree recursively
3. Then right subtree recursively
Use recursion to visit nodes in this order
Output example: 1 2 4 5 3

Full Transcript

Preorder tree traversal means visiting the root node first, then the left subtree, and finally the right subtree. The Rust function uses recursion to do this. Starting at the root, it prints the node's value, then calls itself on the left child, then on the right child. When a node is None, it returns immediately. The execution table shows each step visiting nodes 1, 2, 4, 5, and 3 in that order. The variable tracker shows the current node and the list of visited nodes growing step by step. Key moments clarify why the root is visited first, what happens with missing children, and when traversal ends. The quiz tests understanding of node visits and traversal order changes. This method ensures all nodes are visited in root-left-right order.

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