Tree Traversal Preorder Root Left Right in DSA Rust - Time & Space Complexity

Time Complexity: Tree Traversal Preorder Root Left Right

O(n)

Understanding Time Complexity

We want to understand how long it takes to visit all nodes in a tree using preorder traversal.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn preorder(node: &Option>) {
    if let Some(n) = node {
        println!("{}", n.value);
        preorder(&n.left);
        preorder(&n.right);
    }
}
    

This code visits each node in the tree starting from the root, then left child, then right child.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

Each node is visited exactly one time, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	10 visits
100	100 visits
1000	1000 visits

Pattern observation: The number of operations grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to traverse grows directly in proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "Preorder traversal takes more time because it visits nodes multiple times."

[OK] Correct: Each node is visited exactly once, so the time grows linearly, not more.

Interview Connect

Understanding preorder traversal time helps you explain how tree operations scale, a key skill in many coding interviews.

Self-Check

"What if we changed preorder to inorder traversal? How would the time complexity change?"

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