Traversal Forward and Backward in DSA C++ - Time & Space Complexity

Time Complexity: Traversal Forward and Backward

O(n)

Understanding Time Complexity

We want to understand how long it takes to move through a list from start to end and then back from end to start.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void traverseForwardBackward(int arr[], int n) {
    // Traverse forward
    for (int i = 0; i < n; i++) {
        // process arr[i]
    }
    // Traverse backward
    for (int i = n - 1; i >= 0; i--) {
        // process arr[i]
    }
}
    

This code goes through the array from the first element to the last, then goes back from the last element to the first.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two separate loops each visiting every element once.
• How many times: Each loop runs n times, where n is the size of the array.

How Execution Grows With Input

As the array grows, the total steps grow roughly twice as fast because we go forward and backward.

Input Size (n)	Approx. Operations
10	20 (10 forward + 10 backward)
100	200 (100 forward + 100 backward)
1000	2000 (1000 forward + 1000 backward)

Pattern observation: The total operations grow linearly with input size, doubling because of two passes.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity is O(n²)."

[OK] Correct: The loops run one after another, not nested, so their times add up, not multiply.

Interview Connect

Understanding how multiple passes over data add up helps you explain and optimize code clearly in interviews.

Self-Check

"What if we combined the forward and backward traversal into a single loop that processes two elements per iteration? How would the time complexity change?"

Practice

1. What does forward traversal mean in the context of a singly linked list?

easy

A. Visiting nodes from the head to the tail in order

B. Visiting nodes from the tail to the head in reverse order

C. Skipping every other node while visiting

D. Visiting nodes randomly without order

Solution

1. Step 1: Understand singly linked list structure

   A singly linked list has nodes connected only forward, from head to tail.

2. Step 2: Define forward traversal

   Forward traversal means visiting nodes starting at the head and moving to the tail in order.

3. Final Answer:

   Visiting nodes from the head to the tail in order -> Option A

4. Quick Check:

   Forward traversal = head to tail [OK]

Hint: Forward means start at head and go next nodes [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal can skip nodes
• Assuming random order traversal

2. Which of the following is the correct syntax to traverse a vector forward in C++?

easy

A. for (int i = 0; i < vec.size(); i++) { cout << vec[i] << ' '; }

B. for (int i = vec.size(); i >= 0; i--) { cout << vec[i] << ' '; }

C. for (int i = 1; i <= vec.size(); i++) { cout << vec[i] << ' '; }

D. for (int i = vec.size() - 1; i > 0; i--) { cout << vec[i] << ' '; }

Solution

1. Step 1: Understand vector indexing in C++

   Vectors are zero-indexed, so valid indices are 0 to size()-1.

2. Step 2: Check loop boundaries

   for (int i = 0; i < vec.size(); i++) { cout << vec[i] << ' '; } loops from 0 to size()-1, correctly accessing all elements forward.

3. Final Answer:

   for (int i = 0; i < vec.size(); i++) { cout << vec[i] << ' '; } -> Option A

4. Quick Check:

   Forward vector traversal uses i from 0 to size()-1 [OK]

Hint: Start from 0, go to less than size() for forward loops [OK]

Common Mistakes:

• Using i <= vec.size() causing out-of-range error
• Starting loop from 1 instead of 0
• Looping backwards for forward traversal

3. What is the output of the following C++ code?

std::vector<int> v = {10, 20, 30};
for (int i = v.size() - 1; i >= 0; i--) {
    std::cout << v[i] << ' ';
}

medium

A. 10 20 30

B. 30 20 10

C. 30 20

D. Runtime error

Solution

1. Step 1: Analyze loop start and end

   Loop starts at v.size()-1 = 2 and decrements to 0 inclusive.

2. Step 2: Trace output values

   v[2] = 30, v[1] = 20, v[0] = 10 printed in that order with spaces.

3. Final Answer:

   30 20 10 -> Option B

4. Quick Check:

   Backward traversal prints 30 20 10 [OK]

Hint: Backward vector loop starts at size()-1 down to 0 [OK]

Common Mistakes:

• Confusing forward and backward order
• Off-by-one errors in loop condition
• Expecting runtime error due to unsigned index

4. Identify the error in this backward traversal of a vector in C++:

std::vector<int> v = {1, 2, 3};
for (int i = v.size(); i >= 0; i--) {
    std::cout << v[i] << ' ';
}

medium

A. Vector cannot be traversed backward

B. Loop condition should be i > 0, not i >= 0

C. Loop starts at v.size(), which is out of range

D. No error, code runs fine

Solution

1. Step 1: Check loop start index

   v.size() is 3, but valid indices are 0 to 2, so v[3] is invalid.

2. Step 2: Understand consequences

   Accessing v[3] causes out-of-range error or undefined behavior.

3. Final Answer:

   Loop starts at v.size(), which is out of range -> Option C

4. Quick Check:

   Index must be less than size() [OK]

Hint: Start backward loop at size()-1, not size() [OK]

Common Mistakes:

• Starting loop at size() instead of size()-1
• Ignoring vector index bounds
• Assuming no error on out-of-range access

5. Given a doubly linked list with nodes 1 <-> 2 <-> 3, which code snippet correctly prints the list backward starting from tail in C++?

struct Node {
    int data;
    Node* prev;
    Node* next;
};

Node* tail = /* points to node with data 3 */;
// Which loop prints backward traversal?

hard

A. for (Node* cur = tail; cur->next != nullptr; cur = cur->next) { std::cout << cur->data << ' '; }

B. for (Node* cur = tail; cur != nullptr; cur = cur->next) { std::cout << cur->data << ' '; }

C. for (Node* cur = tail; cur->prev != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; }

D. for (Node* cur = tail; cur != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; }

Solution

1. Step 1: Understand doubly linked list backward traversal

   Backward traversal moves from tail to head using prev pointers.

2. Step 2: Check loop correctness

   for (Node* cur = tail; cur != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; } starts at tail and moves using cur = cur->prev until nullptr, printing all nodes backward.

3. Final Answer:

   for (Node* cur = tail; cur != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; } -> Option D

4. Quick Check:

   Backward traversal uses prev pointer from tail [OK]

Hint: Backward traversal uses prev pointer from tail to head [OK]

Common Mistakes:

• Using next pointer for backward traversal
• Stopping loop before head (checking cur->prev != nullptr)
• Starting from head instead of tail