Reverse Traversal

Definition

Definition

The Reverse Traversal Algorithm is a technique used to traverse through a data structure in reverse order, starting from the end and moving towards the beginning

Explanation

Start from the last element of the data structure and recursively or iteratively moving towards the first element. At each step, it processes the current element and then proceeds to the previous one until it reaches the beginning of the data structure

Guidance

• Identify the data structure you want to traverse in reverse order
• Determine whether you'll use recursion or iteration for the traversal
• Recursive
  • stop recursion when you reach the beginning of the data structure
  • process the current element/node, then call the function recursively with the previous element/node
• Iterative
  • initialize a pointer or index to the last element of the data structure
  • iterate backwards through the data structure, processing each element in reverse order

Tips

• ensure that your base case for recursion properly handles the end condition to prevent infinite recursion
• keep track of the current position or node during traversal to process each element correctly

Practice

Practice

reverseTraversalRecursive(array, currentIndex):
  if currentIndex < 0: # Base case: stop when reaching the beginning of the array
    return
  process(array[currentIndex]) # Process the current element
  reverseTraversal(array, currentIndex - 1) # Recursive step: move to the previous element

reverseTraversalIterative(array):
  endIndex = length(array) - 1
  for i from endIndex to 0: # Iterate backwards through the array
    process(array[i]) # Process each element in reverse order

Solution

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseTraversal(head *ListNode) {
    if head == nil {
        return
    }
    reverseTraversal(head.Next)
    fmt.Println(head.Val)
}

class ListNode {

  int val;
  ListNode next;

  ListNode(int x) {
    val = x;
  }
}

public class Main {

  public void reverseTraversal(ListNode head) {
    if (head == null) {
      return;
    }
    reverseTraversal(head.next);
    System.out.println(head.val);
  }
}

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseTraversal(head) {
  if (head === null) {
    return;
  }
  reverseTraversal(head.next);
  console.log(head.val);
}

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun reverseTraversal(head: ListNode?) {
    if (head == null) return
    reverseTraversal(head.next)
    println(head.`val`)
}

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_traversal(head):
    if head is None:
        return
    reverse_traversal(head.next)
    print(head.val)

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

fn reverse_traversal(head: Option<Box<ListNode>>) {
    if let Some(node) = head {
        reverse_traversal(node.next);
        println!("{}", node.val);
    }
}

class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseTraversal(head: ListNode | null): void {
  if (head === null) return;
  reverseTraversal(head.next);
  console.log(head.val);
}