Skip to main content
Mapagam

Comparing Search and Traversal Patterns

1. Comparing Backtracking vs DP

Aspect Backtracking Dynamic Programming
Approach Explores all possible solutions by building candidates incrementally and abandoning paths that don't lead to a solution. Breaks problem into overlapping subproblems and stores results of subproblems to avoid redundant computations.
State Management Uses recursion or stack to track current state and backtrack when needed. Uses memoization or tabulation to store intermediate results.
Subproblem Overlap Does not typically reuse solutions to subproblems. Relies heavily on overlapping subproblems for efficiency.
Time Complexity Can be exponential in worst case (e.g., N! for permutations). Often reduces time complexity from exponential to polynomial (e.g., O(n^2) for LCS).
Space Complexity O(d) where d is depth of recursion; can be high due to call stack. O(n) for memoization or O(n^2) for 2D DP tables.
Use Cases Problems like N-Queens, Sudoku solvers, generating permutations/combinations. Optimization problems like Longest Common Subsequence, Coin Change, Knapsack.
Solution Type Find one or all valid solutions. Find optimal solution (min/max value).

Example: Solving N-Queens with Backtracking

function solveNQueens(n) {
  const board = Array(n).fill().map(() => Array(n).fill(0));
  const result = [];

  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 1) return false;
      if (col - (row - i) >= 0 && board[i][col - (row - i)] === 1) return false;
      if (col + (row - i) < n && board[i][col + (row - i)] === 1) return false;
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      result.push(board.map(row => [...row]));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 1;
        backtrack(row + 1);
        board[row][col] = 0;
      }
    }
  }

  backtrack(0);
  return result;
}

Example: Coin Change with DP

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Example usage:
console.log(coinChange([1, 3, 4], 6)); // Output: 2 (3 + 3)

Key Differences Summary

  • Backtracking: Recursive exploration with pruning; good for exhaustive search problems.
  • Dynamic Programming: Memoization or tabulation to avoid recomputation; ideal for optimization problems with overlapping subproblems.

2. Comparing Backtracking vs Greedy

Pattern Description Approach Use Cases
Backtracking Explores all possible solutions by building candidates incrementally and abandoning paths that don't lead to a solution. Recursive, exhaustive search with pruning Constraint satisfaction problems, puzzles (e.g., Sudoku), combinatorial optimization
Greedy Makes locally optimal choices at each step, hoping to find a global optimum. Iterative, local optimization Activity selection, Huffman coding, minimum spanning tree (Kruskal's), Dijkstra's algorithm

Example: Solving Subset Sum with Backtracking

function subsetSumBacktrack(nums, target) {
  const result = [];
  
  function backtrack(start, currentSum, path) {
    if (currentSum === target) {
      result.push([...path]);
      return;
    }
    
    for (let i = start; i < nums.length; i++) {
      if (currentSum + nums[i] <= target) {
        path.push(nums[i]);
        backtrack(i + 1, currentSum + nums[i], path);
        path.pop();
      }
    }
  }
  
  backtrack(0, 0, []);
  return result;
}

// Example usage:
const nums = [1, 2, 3, 4];
const target = 5;
console.log(subsetSumBacktrack(nums, target)); // [[1,4], [2,3]]

Example: Activity Selection with Greedy

function activitySelection(activities) {
  // Sort by finish time
  activities.sort((a, b) => a.finish - b.finish);
  
  const selected = [activities[0]];
  let lastFinish = activities[0].finish;
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastFinish) {
      selected.push(activities[i]);
      lastFinish = activities[i].finish;
    }
  }
  
  return selected;
}

// Example usage:
const activities = [
  { name: 'A', start: 1, finish: 4 },
  { name: 'B', start: 3, finish: 5 },
  { name: 'C', start: 0, finish: 6 },
  { name: 'D', start: 5, finish: 7 },
  { name: 'E', start: 3, finish: 9 },
  { name: 'F', start: 5, finish: 9 },
  { name: 'G', start: 6, finish: 10 },
  { name: 'H', start: 8, finish: 11 },
  { name: 'I', start: 8, finish: 12 },
  { name: 'J', start: 2, finish: 14 },
  { name: 'K', start: 12, finish: 16 }
];

console.log(activitySelection(activities));
// Selected: [A, B, D, G, H, K]

Key Differences

  • Backtracking: Systematically explores all possibilities, often with pruning to avoid redundant work.
  • Greedy: Makes the best immediate choice at each step, never reconsidering past decisions.
  • Optimality: Backtracking guarantees finding a solution if one exists; greedy does not always find the optimal solution.

3. Comparing DP vs Greedy

Aspect Dynamic Programming Greedy Algorithm
Approach Breaks problem into overlapping subproblems and solves them optimally Makes locally optimal choices at each step
Optimality Guarantees global optimum for problems with optimal substructure Does not always guarantee global optimum
Time Complexity Often O(n^2) or higher due to memoization/storage Usually O(n log n) or better
Space Complexity Higher due to memoization tables or recursion stack Lower, typically O(1) for simple cases
Problem Types Optimization problems with overlapping subproblems (e.g., Knapsack, LCS) Problems where local choices lead to global solution (e.g., Activity Selection, Huffman Coding)
Decision Making Considers all possibilities before making a decision Makes decisions based on current state without backtracking

Example: Coin Change Problem

function coinChangeDP(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }

  return amount === 0 ? count : -1;
}

// Example usage:
const coins = [1, 3, 4];
const amount = 6;

console.log(coinChangeDP(coins, amount)); // Output: 2 (3 + 3)
console.log(coinChangeGreedy(coins, amount)); // Output: 3 (4 + 1 + 1) - Not optimal

When to Use Which?

  • Use DP when the problem has overlapping subproblems and optimal substructure.
  • Use Greedy when the problem exhibits the greedy choice property and local optimization leads to global optimum.

4. Comparing Memoization vs Tabulation

Aspect Memoization Tabulation
Approach Top-down with caching Bottom-up with table filling
Storage Hash map or array for storing results Table (array) to store subproblem solutions
Recursion May use recursion No recursion
Subproblem Dependencies Only computed subproblems are stored All subproblems computed in order
Space Complexity O(n) for storage + O(n) for recursion stack O(n) for storage only
Time Complexity O(n) average case with memoization O(n) for filling the table
Overhead Higher due to recursive calls Lower, iterative approach
Use Case When subproblems overlap and recursion is natural When all subproblems must be solved in order

Example: Fibonacci Comparison

// Memoization approach
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// Tabulation approach
function fibTab(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

When to Use Which?

  • Memoization is preferred when the recursive structure matches the problem naturally and subproblems are not all needed.
  • Tabulation is preferred when all subproblems must be computed and performance of iterative solutions is desired.

5. Comparing DFS vs BFS

Aspect DFS (Depth-First Search) BFS (Breadth-First Search)
Traversal Order Explores as far as possible down one path before backtracking Explores all neighbors at the current depth before moving to the next level
Data Structure Used Stack (or recursion) Queue
Memory Usage Less memory for wide graphs, more for deep ones Higher memory usage due to storing all nodes at current level
Time Complexity O(V + E) where V = vertices, E = edges O(V + E)
Space Complexity O(V) in worst case (recursion stack) O(V) for storing nodes in queue
Use Cases Path finding, topological sorting, cycle detection Shortest path in unweighted graphs, level-order traversal

Example: DFS Implementation

function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  
  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);
      for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

Example: BFS Implementation

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  
  while (queue.length > 0) {
    const node = queue.shift();
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);
      for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

Key Differences Summary

  • DFS is more memory-efficient for deep graphs but can get stuck in long paths.
  • BFS guarantees shortest path in unweighted graphs but uses more memory.
  • Both have same time complexity O(V + E).

6. Comparing Tree DFS Variants

Variant Description Use Case Code Example
Preorder DFS Visit node, then recursively process left subtree, then right subtree. Tree serialization, copying tree structure. 
function preorder(node) {
  if (!node) return;
  console.log(node.val);
  preorder(node.left);
  preorder(node.right);
}
Inorder DFS Process left subtree, visit node, process right subtree. Binary search tree traversal (sorted order). 
function inorder(node) {
  if (!node) return;
  inorder(node.left);
  console.log(node.val);
  inorder(node.right);
}
Postorder DFS Process left subtree, right subtree, then visit node. Tree deletion, calculating sizes or depths. 
function postorder(node) {
  if (!node) return;
  postorder(node.left);
  postorder(node.right);
  console.log(node.val);
}

Key Differences Summary

  • Preorder: Root first, good for copying or serializing.
  • Inorder: Sorted order in BSTs, ideal for ordered processing.
  • Postorder: Leaves first, useful for tree cleanup or size calculation.

7. Comparing Graph DFS vs BFS

Aspect Depth-First Search (DFS) Breadth-First Search (BFS)
Traversal Order Explores as far as possible along each branch before backtracking Explores all neighbors at the present depth prior to moving to the next depth level
Data Structure Used Stack (or recursion) Queue
Memory Complexity O(h) where h is the maximum depth of the tree O(w) where w is the maximum width of the tree
Time Complexity O(V + E) where V is vertices and E is edges O(V + E) where V is vertices and E is edges
Use Cases Topological sorting, detecting cycles in a graph, solving puzzles like mazes Shortest path in unweighted graphs, level-order traversal, finding connected components
Path Finding Does not guarantee shortest path in unweighted graphs Guarantees shortest path in unweighted graphs

Example: DFS Implementation in JavaScript

function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  
  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);
      for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

Example: BFS Implementation in JavaScript

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  
  while (queue.length > 0) {
    const node = queue.shift();
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);
      for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

Key Differences Summary

  • DFS is more memory-efficient for deep graphs but can get stuck in long paths.
  • BFS guarantees the shortest path in unweighted graphs but uses more memory.
  • Both have same time complexity O(V + E).

8. Comparing Topological Sort Methods

Method Description Time Complexity Space Complexity Use Case
Kahn's Algorithm Uses in-degree tracking and BFS to process nodes with zero in-degrees. O(V + E) O(V) When you need to detect cycles and process nodes in topological order.
DFS-based Uses DFS to detect cycles and build the topological order via post-order traversal. O(V + E) O(V) When you want to detect cycles and build a topological order using recursion.

Example: Kahn's Algorithm Implementation

function topologicalSortKahn(graph) {
  const inDegree = new Array(graph.length).fill(0);
  for (let i = 0; i < graph.length; i++) {
    for (let neighbor of graph[i]) {
      inDegree[neighbor]++;
    }
  }

  const queue = [];
  for (let i = 0; i < inDegree.length; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    for (let neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === graph.length ? result : []; // Return empty if cycle detected
}

Example: DFS-based Implementation

function topologicalSortDFS(graph) {
  const visited = new Array(graph.length).fill(false);
  const recStack = new Array(graph.length).fill(false);
  const stack = [];

  function dfs(node) {
    visited[node] = true;
    recStack[node] = true;

    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) {
        if (dfs(neighbor)) return true;
      } else if (recStack[neighbor]) {
        return true; // Cycle detected
      }
    }

    recStack[node] = false;
    stack.push(node);
    return false;
  }

  for (let i = 0; i < graph.length; i++) {
    if (!visited[i]) {
      if (dfs(i)) return []; // Return empty on cycle
    }
  }

  return stack.reverse();
}

Key Differences

  • Kahn's Algorithm: Iterative, uses queue, easier to understand.
  • DFS-based: Recursive, uses stack for post-order, better for cycle detection.

9. Selecting Search Strategy

Strategy Description Use Case Complexity
Linear Search Sequentially checks each element until the target is found. Small datasets or unsorted data where no preprocessing is allowed. O(n)
Binary Search Divides the sorted array in half repeatedly to find the target. Large sorted datasets where preprocessing is acceptable. O(log n)
Interpolation Search Estimates the position of the target based on value distribution. Uniformly distributed sorted data with known range. O(log log n)
Jump Search Jumps ahead by fixed steps to find the range, then linearly searches. Large sorted arrays where binary search is too complex or costly. O(√n)
Exponential Search Starts with index 1, doubles until the target is found or exceeded. Unbounded or very large sorted arrays where the size is unknown. O(log n) 
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 7;

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

console.log(binarySearch(arr, target)); // Output: 3
Note: Binary search is optimal for sorted arrays, but requires the array to be sorted. Interpolation search can be faster than binary search for uniformly distributed data.

Was this article helpful?

Related Cheat Sheets