Tree Traversal Inorder Left Root Right in DSA Rust

Mental Model

Visit the left side first, then the middle, then the right side in order.

Analogy: Like reading a book where you first look at the left page, then the center page, then the right page.

    2
   / \
  1   3
↑root

Dry Run Walkthrough

Input: Tree: root=2, left=1, right=3; perform inorder traversal

Goal: Print nodes in order: left child, root, right child

Step 1: Go to left child of root (2)

    2
   / \
  [1]  3
↑curr at 1

Why: Inorder means visit left subtree first

Step 2: Left child of 1 is null, print 1

Output: 1

Why: No more left nodes, so print current node

Step 3: Return to root (2), print 2

Output: 1 2

Why: After left subtree, print root

Step 4: Go to right child of root (3)

    2
   / \
   1  [3]
↑curr at 3

Why: After root, visit right subtree

Step 5: Left child of 3 is null, print 3

Output: 1 2 3

Why: No more left nodes, print current node

Result:

Output: 1 2 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 inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        // Traverse left subtree
        inorder_traversal(node.borrow().left.clone());
        // Visit root
        print!("{} ", node.borrow().val);
        // Traverse right subtree
        inorder_traversal(node.borrow().right.clone());
    }
}

fn main() {
    // Build tree: 2
    //           / \
    //          1   3
    let root = TreeNode::new(2);
    root.borrow_mut().left = Some(TreeNode::new(1));
    root.borrow_mut().right = Some(TreeNode::new(3));

    inorder_traversal(Some(root));
    println!();
}

inorder_traversal(node.borrow().left.clone());

Traverse left subtree first to reach smallest values

print!("{} ", node.borrow().val);

Print current node value after left subtree

inorder_traversal(node.borrow().right.clone());

Traverse right subtree last

Output

1 2 3 

Complexity Analysis

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

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to preorder or postorder, inorder also visits all nodes once but order differs; iterative methods may use explicit stack increasing space

Edge Cases

Empty tree (root is None)

No output, function returns immediately

DSA Rust

if let Some(node) = root {

Single node tree

Prints the single node value

DSA Rust

print!("{} ", node.borrow().val);

Left skewed tree (all nodes only have left child)

Prints nodes in ascending order from bottom left to root

DSA Rust

inorder_traversal(node.borrow().left.clone());

When to Use This Pattern

When you need to process a binary tree in sorted order or left-root-right order, use inorder traversal because it visits nodes in ascending order for binary search trees.

Common Mistakes

Mistake: Visiting root before left subtree (preorder) instead of after
Fix: Call left subtree traversal before printing root value

Mistake: Forgetting to clone Rc pointers causing borrow errors
Fix: Use .clone() on Rc pointers when passing to recursive calls

Summary

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

Use when you want nodes in ascending order from a binary search tree.

The key is to recursively visit left first, then root, then right.

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