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

Concept Flow - Tree Traversal Inorder Left Root Right

Start at root node

↓

Traverse left subtree

↓

Visit current node (root)

↓

Traverse right subtree

↓

End

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

Execution Sample

DSA Rust

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

This code recursively visits nodes in the order: left child, root, right child.

Execution Table

Step	Operation	Node Visited	Action	Tree State (Visual)
1	Start at root	1	Traverse left subtree	1 / \ 2 3
2	Traverse left subtree	2	Traverse left subtree	1 / \ 2 3 / 4
3	Traverse left subtree	4	Traverse left subtree (None)	1 / \ 2 3 / 4
4	Left subtree None	None	Return	1 / \ 2 3 / 4
5	Visit node	4	Print 4	1 / \ 2 3 / 4
6	Traverse right subtree	4	Traverse right subtree (None)	1 / \ 2 3 / 4
7	Right subtree None	None	Return	1 / \ 2 3 / 4
8	Return to node	2	Print 2	1 / \ 2 3 / 4
9	Traverse right subtree	2	Traverse right subtree (None)	1 / \ 2 3 / 4
10	Right subtree None	None	Return	1 / \ 2 3 / 4
11	Return to root	1	Print 1	1 / \ 2 3 / 4
12	Traverse right subtree	1	Traverse right subtree	1 / \ 2 3 / 4 \ 5
13	Traverse left subtree	3	Traverse left subtree (None)	1 / \ 2 3 / 4 \ 5
14	Left subtree None	None	Return	1 / \ 2 3 / 4 \ 5
15	Visit node	3	Print 3	1 / \ 2 3 / 4 \ 5
16	Traverse right subtree	3	Traverse right subtree	1 / \ 2 3 / 4 \ 5
17	Traverse left subtree	5	Traverse left subtree (None)	1 / \ 2 3 / 4 \ 5
18	Left subtree None	None	Return	1 / \ 2 3 / 4 \ 5
19	Visit node	5	Print 5	1 / \ 2 3 / 4 \ 5
20	Traverse right subtree	5	Traverse right subtree (None)	1 / \ 2 3 / 4 \ 5
21	Right subtree None	None	Return	1 / \ 2 3 / 4 \ 5
22	Traversal complete	None	End	1 / \ 2 3 / 4 \ 5

💡 Traversal ends after visiting all nodes in left-root-right order.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 15	After Step 19	Final
Current Node	1	2	4	2	1	3	5	None
Printed Values	[]	[]	[4]	[4, 2]	[4, 2, 1]	[4, 2, 1, 3]	[4, 2, 1, 3, 5]	[4, 2, 1, 3, 5]

Key Moments - 3 Insights

Why do we visit the left subtree before printing the root node?

Because inorder traversal means Left, Root, Right. The execution_table rows 2-5 show we go deep left first before printing the node.

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

The traversal returns immediately without printing anything, as shown in steps 3-4 and 6-7 where left or right subtree is None.

Why do we print the node value after traversing the left subtree?

Because inorder traversal prints the root after the left subtree is fully visited, as seen in step 5 for node 4 and step 8 for node 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the printed output after step 8?

A [2]

B [4]

C [4, 2]

D [1]

💡 Hint

Check the 'Printed Values' row in variable_tracker after step 8.

At which step does the traversal visit the root node (value 1)?

A Step 11

B Step 5

C Step 8

D Step 15

💡 Hint

Look at the 'Node Visited' and 'Action' columns in execution_table.

If the left child of node 2 was None, how would the printed output after step 8 change?

A [4]

B [2]

C [4, 2]

D [1]

💡 Hint

Without left subtree for node 2, node 4 is never visited, so only node 2 is printed before step 8.

Concept Snapshot

Inorder Tree Traversal:
- Visit left subtree first
- Then visit root node
- Finally visit right subtree
Recursive approach is common
Print nodes in ascending order for BST

Full Transcript

Inorder traversal visits nodes in the order left subtree, root, then right subtree. Starting at the root, we recursively go left until no more left children. Then we print the node value, and move to the right subtree. This process repeats until all nodes are visited. The example tree has nodes 1 as root, 2 as left child with 4 as its left child, and 3 as right child with 5 as its right child. The printed output order is 4, 2, 1, 3, 5. The traversal uses recursion to handle each subtree. When a subtree is None, the function returns immediately. This ensures all nodes are visited in the correct order.

Practice

1. What is the order of nodes visited in an inorder traversal of a binary tree?

easy

A. Left subtree, Root node, Right subtree

B. Root node, Left subtree, Right subtree

C. Right subtree, Root node, Left subtree

D. Root node, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits nodes in the order: left subtree first, then the root node, and finally the right subtree.

2. Step 2: Match the order with options

   Left subtree, Root node, Right subtree matches the left-root-right order exactly.

3. Final Answer:

   Left subtree, Root node, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder means Left, Root, then Right [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Mixing up the order of root and subtrees
• Thinking inorder visits root first

2. Which Rust code snippet correctly implements the inorder traversal function signature for a binary tree node?

easy

A. fn inorder(node: Box<TreeNode>) -> Vec<i32> { /* traversal code */ }

B. fn inorder(node: &Option) { /* traversal code */ }

C. fn inorder(node: &TreeNode) -> Vec<i32> { /* traversal code */ }

D. fn inorder(node: Option<TreeNode>) { /* traversal code */ }

Solution

1. Step 1: Understand Rust ownership and references for trees

   Binary trees in Rust often use Option to allow null and heap allocation. Passing by reference (&Option) avoids ownership transfer during traversal.

2. Step 2: Check each option's signature

   fn inorder(node: &Option) { /* traversal code */ } uses a reference to Option, which is correct for traversal without ownership moves. Others either take ownership or incorrect types.

3. Final Answer:

   fn inorder(node: &Option) { /* traversal code */ } -> Option B

4. Quick Check:

   Use &Option for safe traversal [OK]

Hint: Use references to Option for traversal [OK]

Common Mistakes:

• Taking ownership of nodes causing move errors
• Using plain TreeNode instead of Box or Option
• Returning traversal result without proper ownership

3. Given the following Rust code for inorder traversal, what is the printed output?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

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

fn main() {
    let tree = Some(Box::new(TreeNode {
        val: 2,
        left: Some(Box::new(TreeNode {
            val: 1,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: None,
        })),
    }));
    inorder(&tree);
}

medium

A. 3 2 1

B. 2 1 3

C. 1 2 3

D. 1 3 2

Solution

1. Step 1: Understand the tree structure

   The root node has value 2, left child 1, right child 3.

2. Step 2: Trace inorder traversal

   Inorder visits left subtree (1), then root (2), then right subtree (3). So output is "1 2 3 "

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Inorder prints left-root-right: 1 2 3 [OK]

Hint: Inorder prints left child, root, then right child [OK]

Common Mistakes:

• Printing root before left subtree
• Confusing preorder or postorder output
• Ignoring spaces in output

4. Identify the error in this Rust inorder traversal code and select the fix:

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

medium

A. No error, code is correct

B. Change parameter to Option<&Box<TreeNode>> and call inorder(n.left) and inorder(n.right)

C. Add return type Vec<i32> and collect values instead of printing

D. Change parameter to &Option and call inorder(&n.left) and inorder(&n.right)

Solution

1. Step 1: Identify ownership problem in parameter

   The function takes ownership of node, so recursive calls move ownership of n.left and n.right, which is invalid after first call.

2. Step 2: Fix by using references

   Changing parameter to &Option and calling inorder(&n.left) and inorder(&n.right) avoids ownership moves and allows safe recursion.

3. Final Answer:

   Change parameter to &Option and call inorder(&n.left) and inorder(&n.right) -> Option D

4. Quick Check:

   Use references to avoid ownership moves in recursion [OK]

Hint: Use references in recursive tree traversal to avoid ownership errors [OK]

Common Mistakes:

• Passing ownership causing move errors
• Trying to use Option<&Box<TreeNode>> incorrectly
• Ignoring Rust's ownership rules in recursion

5. You want to collect all values of a binary tree in inorder traversal into a vector in Rust. Which code snippet correctly implements this?

hard

A. fn inorder_collect(node: &Option) -> Vec<i32> {
let mut vals = Vec::new();
if let Some(n) = node {
vals.extend(inorder_collect(&n.left));
vals.push(n.val);
vals.extend(inorder_collect(&n.right));
}
vals
}

B. fn inorder_collect(node: Option) -> Vec<i32> {
let mut vals = Vec::new();
if let Some(n) = node {
vals.push(n.val);
vals.extend(inorder_collect(n.left));
vals.extend(inorder_collect(n.right));
}
vals
}

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

D. fn inorder_collect(node: &Option) -> Vec<i32> {
let mut vals = Vec::new();
if let Some(n) = node {
vals.push(n.val);
vals.extend(inorder_collect(&n.right));
vals.extend(inorder_collect(&n.left));
}
vals
}

Solution

1. Step 1: Understand inorder traversal collection

   Inorder means collect left subtree values first, then root value, then right subtree values.

2. Step 2: Check each code snippet's order and ownership

   fn inorder_collect(node: &Option) -> Vec<i32> { let mut vals = Vec::new(); if let Some(n) = node { vals.extend(inorder_collect(&n.left)); vals.push(n.val); vals.extend(inorder_collect(&n.right)); } vals } correctly uses references, collects left subtree, then root, then right subtree, returning combined vector.

3. Final Answer:

   fn inorder_collect(node: &Option) -> Vec<i32> { let mut vals = Vec::new(); if let Some(n) = node { vals.extend(inorder_collect(&n.left)); vals.push(n.val); vals.extend(inorder_collect(&n.right)); } vals } -> Option A

4. Quick Check:

   Collect left, root, right in vector [OK]

Hint: Collect left subtree, then root, then right subtree values [OK]

Common Mistakes:

• Wrong order of pushing values
• Taking ownership instead of references
• Appending right subtree before left