Traversal Forward and Backward in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Forward Traversal in Doubly Linked List

What is the output of the following C++ code that traverses a doubly linked list forward?

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

int main() {
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "null" << endl;
    return 0;
}

A 1 -> 3 -> 2 -> null

B 3 -> 2 -> 1 -> null

C null -> 1 -> 2 -> 3

D 1 -> 2 -> 3 -> null

💡 Hint

Start from the head and move using the next pointer.

The code starts from the head node and moves forward using the next pointer, printing each node's data. So the output is the sequence 1, 2, 3 followed by null.

❓ Predict Output

intermediate

Output of Backward Traversal in Doubly Linked List

What is the output of the following C++ code that traverses a doubly linked list backward?

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

int main() {
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    Node* current = third;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->prev;
    }
    cout << "null" << endl;
    return 0;
}

A 1 -> 2 -> 3 -> null

B 3 -> 2 -> 1 -> null

C null -> 3 -> 2 -> 1

D 2 -> 3 -> 1 -> null

💡 Hint

Start from the tail and move using the prev pointer.

The code starts from the last node (third) and moves backward using the prev pointer, printing each node's data. So the output is 3, 2, 1 followed by null.

🧠 Conceptual

advanced

Understanding Traversal Pointers in Doubly Linked List

In a doubly linked list, which pointer is used to move backward during traversal?

A prev pointer

B head pointer

C tail pointer

D next pointer

💡 Hint

Backward means going to the previous node.

The prev pointer in each node points to the previous node, allowing backward traversal.

🔧 Debug

advanced

Identify the Bug in Backward Traversal Code

What error will occur when running this code snippet for backward traversal of a doubly linked list?

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

int main() {
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    Node* current = head;
    while (current != nullptr) {
        current = current->prev;
        cout << current->data << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

A Syntax error: missing semicolon

B No output, infinite loop

C Runtime error due to null pointer dereference

D Correct output: 1 -> 2 -> 3 -> null

💡 Hint

Check the pointer used for traversal starting from head.

Starting backward traversal from head uses prev pointer which is nullptr, so next iteration tries to access prev of nullptr causing runtime error.

🚀 Application

expert

Resulting List After Mixed Forward and Backward Traversal

Given a doubly linked list with nodes 10 <-> 20 <-> 30 <-> 40, what is the printed output after this traversal sequence? 1. Traverse forward from head to tail printing nodes. 2. Then traverse backward from tail to head printing nodes.

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

int main() {
    Node* n1 = new Node(10);
    Node* n2 = new Node(20);
    Node* n3 = new Node(30);
    Node* n4 = new Node(40);

    n1->next = n2;
    n2->prev = n1;
    n2->next = n3;
    n3->prev = n2;
    n3->next = n4;
    n4->prev = n3;

    Node* current = n1;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "null" << endl;

    current = n4;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->prev;
    }
    cout << "null" << endl;

    return 0;
}

A

10 -> 20 -> 30 -> 40 -> null
40 -> 30 -> 20 -> 10 -> null

B

40 -> 30 -> 20 -> 10 -> null
10 -> 20 -> 30 -> 40 -> null

C

10 -> 20 -> 30 -> 40 -> null
10 -> 20 -> 30 -> 40 -> null

D

40 -> 30 -> 20 -> 10 -> null
40 -> 30 -> 20 -> 10 -> null

💡 Hint

First print forward from head, then backward from tail.

The first loop prints nodes from head to tail: 10, 20, 30, 40. The second loop prints nodes from tail to head: 40, 30, 20, 10.

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