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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Forward Traversal in Doubly Linked List

What is the printed output after traversing the doubly linked list forward from head to tail?

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  prev: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  traverseForward() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.traverseForward();

A null -> 10 -> 20 -> 30

B 30 -> 20 -> 10 -> null

C 10 -> 20 -> 30 -> null

D 10 -> 30 -> 20 -> null

💡 Hint

Start from the head and move to the next node until you reach null.

The forward traversal starts at the head node (10) and moves through next pointers: 10 to 20 to 30, then null.

❓ Predict Output

intermediate

Output of Backward Traversal in Doubly Linked List

What is the printed output after traversing the doubly linked list backward from tail to head?

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  prev: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  traverseBackward() {
    let current = this.tail;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.prev;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new DoublyLinkedList();
list.append(5);
list.append(15);
list.append(25);
list.traverseBackward();

A 25 -> 15 -> 5 -> null

B 5 -> 15 -> 25 -> null

C null -> 25 -> 15 -> 5

D 15 -> 5 -> 25 -> null

💡 Hint

Start from the tail and move to the previous node until you reach null.

The backward traversal starts at the tail node (25) and moves through prev pointers: 25 to 15 to 5, then null.

🧠 Conceptual

advanced

Understanding Traversal Direction Impact

Which statement best explains the difference between forward and backward traversal in a doubly linked list?

A Forward traversal uses next pointers from head to tail; backward traversal uses prev pointers from tail to head.

B Forward traversal uses prev pointers from tail to head; backward traversal uses next pointers from head to tail.

C Both traversals use next pointers but start at different nodes.

D Both traversals use prev pointers but start at different nodes.

💡 Hint

Think about which pointers connect nodes forward and backward.

In a doubly linked list, each node has a next pointer to the next node and a prev pointer to the previous node. Forward traversal follows next pointers from head to tail, backward traversal follows prev pointers from tail to head.

🔧 Debug

advanced

Identify the Bug in Backward Traversal

What error will occur when running this backward traversal code snippet?

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  prev: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  traverseBackward() {
    let current = this.head; // Bug here: should start from tail
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.prev;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.traverseBackward();

A Infinite loop

B Runtime error: Cannot read property 'prev' of null

C Output: 3 -> 2 -> 1 -> null

D Output: 1 -> null

💡 Hint

Check where the traversal starts and which pointer it follows.

The traversal starts at head but moves using prev pointers which are null at head, so it prints only the head value then stops.

🚀 Application

expert

Result of Mixed Forward and Backward Traversal

Given the doubly linked list with values [7, 14, 21], what is the output after this code runs?

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  prev: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  traverseMixed() {
    let current = this.head;
    let result = '';
    while (current && current.next) {
      result += current.value + ' -> ';
      current = current.next;
    }
    // Now traverse backward one step
    if (current) {
      result += current.value + ' -> ';
      current = current.prev;
    }
    if (current) {
      result += current.value + ' -> ';
    }
    result += 'null';
    console.log(result);
  }
}

const list = new DoublyLinkedList();
list.append(7);
list.append(14);
list.append(21);
list.traverseMixed();

A 7 -> 14 -> 21 -> 7 -> null

B 7 -> 14 -> 21 -> 14 -> null

C 21 -> 14 -> 7 -> null

D 7 -> 14 -> null

💡 Hint

Follow the forward traversal to the last node, then one step backward.

The code moves forward from head to tail printing 7, 14, 21, then moves one step backward to 14 and prints it before ending.

Practice

1. What does forward traversal in a linked list mean?

easy

A. Visiting nodes randomly without order

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

C. Skipping every other node while traversing

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

Solution

1. Step 1: Understand linked list structure

   A linked list has nodes connected from head to tail in one direction.

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 D

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 is random
• Assuming skipping nodes is traversal

2. Which TypeScript syntax correctly traverses an array forward using a for loop?

easy

A. for(let i = arr.length; i >= 0; i--) { console.log(arr[i]); }

B. for(let i = 0; i < arr.length; i++) { console.log(arr[i]); }

C. for(let i = 1; i <= arr.length; i++) { console.log(arr[i]); }

D. for(let i = arr.length - 1; i > 0; i--) { console.log(arr[i]); }

Solution

1. Step 1: Identify forward traversal loop

   Forward traversal starts at index 0 and goes up to length-1.

2. Step 2: Check loop conditions

   for(let i = 0; i < arr.length; i++) { console.log(arr[i]); } loops from 0 to less than arr.length, printing each element correctly.

3. Final Answer:

   for(let i = 0; i < arr.length; i++) { console.log(arr[i]); } -> Option B

4. Quick Check:

   Forward loop index from 0 to length-1 [OK]

Hint: Start index 0, end before length for forward loop [OK]

Common Mistakes:

• Starting index at 1 instead of 0
• Using i <= arr.length causing out-of-bounds
• Looping backward for forward traversal

3. What is the output of this TypeScript code?

const arr = [10, 20, 30];
for(let i = arr.length - 1; i >= 0; i--) {
  console.log(arr[i]);
}

medium

A. 30 20 10

B. 10 20 30

C. 30 20

D. Error: Index out of bounds

Solution

1. Step 1: Understand loop start and end

   The loop starts at index 2 (arr.length - 1) and goes down to 0.

2. Step 2: Trace output values

   It prints arr[2] = 30, arr[1] = 20, arr[0] = 10 in that order.

3. Final Answer:

   30 20 10 -> Option A

4. Quick Check:

   Backward traversal prints 30 20 10 [OK]

Hint: Backward loop starts at length-1 down to 0 [OK]

Common Mistakes:

• Thinking output is forward order
• Missing last element at index 0
• Assuming error due to loop

4. Identify the error in this backward traversal code for a linked list:

let current = head;
while(current !== null) {
  console.log(current.value);
  current = current.prev;
}

medium

A. It should use current.next instead of current.prev

B. No error, code is correct

C. It should start from tail, not head

D. It should check current.next !== null in while condition

Solution

1. Step 1: Understand backward traversal in linked list

   Backward traversal uses prev pointers starting from the tail node.

2. Step 2: Check starting node

   The code starts at head, but to go backward, it must start at tail.

3. Final Answer:

   It should start from tail, not head -> Option C

4. Quick Check:

   Backward traversal starts at tail [OK]

Hint: Backward traversal must start at tail node [OK]

Common Mistakes:

• Starting backward traversal at head
• Using next instead of prev for backward
• Wrong loop condition check

5. Given a doubly linked list, how would you print all values backward starting from the head node?

hard

A. Traverse forward to tail, then traverse backward from tail to head

B. Traverse backward directly from head using prev pointers

C. Use only next pointers starting from head to print backward

D. Reverse the list first, then traverse forward

Solution

1. Step 1: Understand doubly linked list structure

   Each node has next and prev pointers; head has no prev, tail has no next.

2. Step 2: Plan backward print from head

   To print backward from head, first move forward to tail using next pointers.

3. Step 3: Traverse backward from tail

   From tail, use prev pointers to print nodes backward to head.

4. Final Answer:

   Traverse forward to tail, then traverse backward from tail to head -> Option A

5. Quick Check:

   Backward print from head requires forward then backward traversal [OK]

Hint: Go forward to tail, then backward to print [OK]

Common Mistakes:

• Trying to go backward directly from head
• Using next pointers to print backward
• Reversing list unnecessarily