Traversal Forward and Backward in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Forward and Backward Traversal in Doubly Linked List

What is the printed output after running the following code that traverses a doubly linked list forward and then backward?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def traverse_forward(self):
        current = self.head
        result = []
        while current:
            result.append(str(current.val))
            current = current.next
        return ' -> '.join(result) + ' -> null'

    def traverse_backward(self):
        current = self.tail
        result = []
        while current:
            result.append(str(current.val))
            current = current.prev
        return ' -> '.join(result) + ' -> null'

# Create list and append values
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)

# Print forward and backward traversal
print(dll.traverse_forward())
print(dll.traverse_backward())

A "10 -> 20 -> 30 -> null\n10 -> 20 -> 30 -> null"

B "10 -> 20 -> 30 -> null\n30 -> 20 -> 10 -> null"

C "30 -> 20 -> 10 -> null\n10 -> 20 -> 30 -> null"

D "30 -> 20 -> 10 -> null\n30 -> 20 -> 10 -> null"

💡 Hint

Think about how the doubly linked list stores references to both next and previous nodes.

The forward traversal prints nodes from head to tail: 10 -> 20 -> 30 -> null. The backward traversal prints nodes from tail to head: 30 -> 20 -> 10 -> null.

🧠 Conceptual

intermediate

Understanding Traversal Direction in Doubly Linked Lists

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

A The 'next' pointer

B The 'tail' pointer

C The 'head' pointer

D The 'prev' 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 Error in Backward Traversal Code

What is wrong with this backward traversal code snippet on a doubly linked list?

DSA Python

def traverse_backward(head):
    current = head
    result = []
    while current:
        result.append(str(current.val))
        current = current.prev
    return ' -> '.join(result) + ' -> null'

# Assume doubly linked list with head node exists

A "Logical error: starts from 'head' instead of 'tail', only visits the head node"

B Infinite loop because current never becomes None

C No error, returns correct backward traversal

D TypeError because 'prev' is not a valid attribute

💡 Hint

Think about the starting point for backward traversal.

Backward traversal must start from the tail node, not the head. Starting at head only visits the head node since head.prev is None immediately after the first iteration. No runtime error occurs.

❓ Predict Output

advanced

Output After Mixed Forward and Backward Traversal

What is the output of the following code that traverses a doubly linked list forward, then backward, then forward again?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def traverse_forward(self):
        current = self.head
        result = []
        while current:
            result.append(str(current.val))
            current = current.next
        return ' -> '.join(result) + ' -> null'

    def traverse_backward(self):
        current = self.tail
        result = []
        while current:
            result.append(str(current.val))
            current = current.prev
        return ' -> '.join(result) + ' -> null'

# Create list and append values
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)

print(dll.traverse_forward())
print(dll.traverse_backward())
print(dll.traverse_forward())

A "1 -> 2 -> 3 -> null\n1 -> 2 -> 3 -> null\n3 -> 2 -> 1 -> null"

B "3 -> 2 -> 1 -> null\n1 -> 2 -> 3 -> null\n3 -> 2 -> 1 -> null"

C "1 -> 2 -> 3 -> null\n3 -> 2 -> 1 -> null\n1 -> 2 -> 3 -> null"

D "3 -> 2 -> 1 -> null\n3 -> 2 -> 1 -> null\n1 -> 2 -> 3 -> null"

💡 Hint

The list does not change between traversals.

The list is traversed forward (1->2->3), then backward (3->2->1), then forward again (1->2->3).

🚀 Application

expert

Number of Nodes Visited in Mixed Traversal

Given a doubly linked list with 5 nodes, if you traverse forward 3 nodes starting from head, then backward 2 nodes, how many unique nodes have you visited in total?

A 3 unique nodes

B 4 unique nodes

C 5 unique nodes

D 2 unique nodes

💡 Hint

Count nodes visited without repeating.

Assume nodes labeled 1-2-3-4-5. Forward traversal visits nodes 1, 2, 3 (ending at 3). Backward 2 nodes from there visits 2, then 1. Unique nodes: 1, 2, 3.

Practice

1. What does traversal forward mean when moving through a list?

easy

A. Visiting elements randomly

B. Visiting elements from the last to the first

C. Visiting elements from the first to the last

D. Skipping every other element

Solution

1. Step 1: Understand traversal direction

   Traversal forward means starting at the beginning of the list and moving step-by-step to the end.

2. Step 2: Compare options

   Only Visiting elements from the first to the last describes visiting elements from first to last, which matches forward traversal.

3. Final Answer:

   Visiting elements from the first to the last -> Option C

4. Quick Check:

   Forward traversal = first to last [OK]

Hint: Forward means start to end in order [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal means skipping elements
• Assuming traversal is random

2. Which of the following Python loops correctly traverses a list items backward?

easy

A. for i in range(len(items)): print(items[i])

B. for i in range(len(items)-1, -1, -1): print(items[i])

C. for i in items: print(i)

D. for i in range(0, len(items), 2): print(items[i])

Solution

1. Step 1: Identify backward traversal syntax

   Backward traversal uses a loop that starts from the last index and moves to the first, decreasing the index.

2. Step 2: Check each option

   for i in range(len(items)-1, -1, -1): print(items[i]) uses range(len(items)-1, -1, -1), which counts backward correctly.

3. Final Answer:

   for i in range(len(items)-1, -1, -1): print(items[i]) -> Option B

4. Quick Check:

   Backward loop uses decreasing range [OK]

Hint: Use range with step -1 for backward loops [OK]

Common Mistakes:

• Using range(len(items)) for backward traversal
• Forgetting to set step as -1
• Using direct iteration which is forward only

3. What is the output of this code?

items = [10, 20, 30]
for i in range(len(items)-1, -1, -1):
    print(items[i], end=' ')

medium

A. 30 20 10

B. 10 20 30

C. 0 1 2

D. SyntaxError

Solution

1. Step 1: Understand the loop range

   The loop runs from index 2 down to 0 (inclusive), so it visits indices 2, 1, 0 in order.

2. Step 2: Print elements in backward order

   items[2] = 30, items[1] = 20, items[0] = 10, printed with spaces.

3. Final Answer:

   30 20 10 -> Option A

4. Quick Check:

   Backward print = 30 20 10 [OK]

Hint: Backward range prints list in reverse order [OK]

Common Mistakes:

• Confusing index order and printing forward
• Misreading range parameters
• Expecting index numbers instead of list values

4. Find the error in this backward traversal code:

items = [1, 2, 3, 4]
for i in range(len(items)):
    print(items[len(items)-i])

medium

A. IndexError due to out-of-range index

B. SyntaxError because of missing colon

C. Prints elements forward instead of backward

D. No error, prints backward correctly

Solution

1. Step 1: Analyze index calculation

   Index used is len(items)-i. For i=0, index is 4, which is out of range (max index 3).

2. Step 2: Identify error type

   Accessing index 4 causes IndexError because list indices go from 0 to 3.

3. Final Answer:

   IndexError due to out-of-range index -> Option A

4. Quick Check:

   Index out of range = IndexError [OK]

Hint: Check if index goes beyond list length [OK]

Common Mistakes:

• Using len(items)-i instead of len(items)-1-i
• Ignoring zero-based indexing
• Assuming no error if code runs partially

5. Given a doubly linked list with nodes head and tail, which approach correctly prints all elements forward then backward?

hard

A. Traverse from tail to head, then from head to tail

B. Traverse only from head to tail twice

C. Traverse randomly from any node

D. Traverse from head to tail printing, then from tail to head printing

Solution

1. Step 1: Understand doubly linked list traversal

   Doubly linked lists allow moving forward from head to tail and backward from tail to head using next and prev pointers.

2. Step 2: Identify correct traversal order

   To print forward then backward, first traverse from head to tail, then from tail to head.

3. Final Answer:

   Traverse from head to tail printing, then from tail to head printing -> Option D

4. Quick Check:

   Forward then backward traversal = head to tail, tail to head [OK]

Hint: Use head-to-tail then tail-to-head for full traversal [OK]

Common Mistakes:

• Trying to traverse backward without tail pointer
• Traversing forward twice instead of backward
• Assuming singly linked list can traverse backward