Binary TreesBinary Trees36
  1. 1Preorder Traversal of a Binary Tree using Recursion
  2. 2Preorder Traversal of a Binary Tree using Iteration
  3. 3Inorder Traversal of a Binary Tree using Recursion
  4. 4Inorder Traversal of a Binary Tree using Iteration
  5. 5Postorder Traversal of a Binary Tree Using Recursion
  6. 6Postorder Traversal of a Binary Tree using Iteration
  7. 7Level Order Traversal of a Binary Tree using Recursion
  8. 8Level Order Traversal of a Binary Tree using Iteration
  9. 9Reverse Level Order Traversal of a Binary Tree using Iteration
  10. 10Reverse Level Order Traversal of a Binary Tree using Recursion
  11. 11Find Height of a Binary Tree
  12. 12Find Diameter of a Binary Tree
  13. 13Find Mirror of a Binary Tree
  14. 14Left View of a Binary Tree
  15. 15Right View of a Binary Tree
  16. 16Top View of a Binary Tree
  17. 17Bottom View of a Binary Tree
  18. 18Zigzag Traversal of a Binary Tree
  19. 19Check if a Binary Tree is Balanced
  20. 20Diagonal Traversal of a Binary Tree
  21. 21Boundary Traversal of a Binary Tree
  22. 22Construct a Binary Tree from a String with Bracket Representation
  23. 23Convert a Binary Tree into a Doubly Linked List
  24. 24Convert a Binary Tree into a Sum Tree
  25. 25Find Minimum Swaps Required to Convert a Binary Tree into a BST
  26. 26Check if a Binary Tree is a Sum Tree
  27. 27Check if All Leaf Nodes are at the Same Level in a Binary Tree
  28. 28Lowest Common Ancestor (LCA) in a Binary Tree
  29. 29Solve the Tree Isomorphism Problem
  30. 30Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More
  31. 31Check if Two Binary Trees are Mirror Images
  32. 32Calculate the Sum of Nodes on the Longest Path from Root to Leaf in a Binary Tree
  33. 33Print All Paths in a Binary Tree with a Given Sum
  34. 34Find the Distance Between Two Nodes in a Binary Tree
  35. 35Find the kth Ancestor of a Node in a Binary Tree
  36. 36Find All Duplicate Subtrees in a Binary Tree
GraphsGraphs46
  1. 1Breadth-First Search in Graphs
  2. 2Depth-First Search in Graphs
  3. 3Number of Provinces in an Undirected Graph
  4. 4Connected Components in a Matrix
  5. 5Rotten Oranges Problem - BFS in Matrix
  6. 6Flood Fill Algorithm - Graph Based
  7. 7Detect Cycle in an Undirected Graph using DFS
  8. 8Detect Cycle in an Undirected Graph using BFS
  9. 9Distance of Nearest Cell Having 1 - Grid BFS
  10. 10Surrounded Regions in Matrix using Graph Traversal
  11. 11Number of Enclaves in Grid
  12. 12Word Ladder - Shortest Transformation using Graph
  13. 13Word Ladder II - All Shortest Transformation Sequences
  14. 14Number of Distinct Islands using DFS
  15. 15Check if a Graph is Bipartite using DFS
  16. 16Topological Sort Using DFS
  17. 17Topological Sort using Kahn's Algorithm
  18. 18Cycle Detection in Directed Graph using BFS
  19. 19Course Schedule - Task Ordering with Prerequisites
  20. 20Course Schedule 2 - Task Ordering Using Topological Sort
  21. 21Find Eventual Safe States in a Directed Graph
  22. 22Alien Dictionary Character Order
  23. 23Shortest Path in Undirected Graph with Unit Distance
  24. 24Shortest Path in DAG using Topological Sort
  25. 25Dijkstra's Algorithm Using Set - Shortest Path in Graph
  26. 26Dijkstra’s Algorithm Using Priority Queue
  27. 27Shortest Distance in a Binary Maze using BFS
  28. 28Path With Minimum Effort in Grid using Graphs
  29. 29Cheapest Flights Within K Stops - Graph Problem
  30. 30Number of Ways to Reach Destination in Shortest Time - Graph Problem
  31. 31Minimum Multiplications to Reach End - Graph BFS
  32. 32Bellman-Ford Algorithm for Shortest Paths
  33. 33Floyd Warshall Algorithm for All-Pairs Shortest Path
  34. 34Find the City With the Fewest Reachable Neighbours
  35. 35Minimum Spanning Tree in Graphs
  36. 36Prim's Algorithm for Minimum Spanning Tree
  37. 37Disjoint Set (Union-Find) with Union by Rank and Path Compression
  38. 38Kruskal's Algorithm - Minimum Spanning Tree
  39. 39Minimum Operations to Make Network Connected
  40. 40Most Stones Removed with Same Row or Column
  41. 41Accounts Merge Problem using Disjoint Set Union
  42. 42Number of Islands II - Online Queries using DSU
  43. 43Making a Large Island Using DSU
  44. 44Bridges in Graph using Tarjan's Algorithm
  45. 45Articulation Points in Graphs
  46. 46Strongly Connected Components using Kosaraju's Algorithm

Word Ladder - II Find All Shortest Transformation Sequences

Problem Statement

Given two words, startWord and targetWord, and a list of unique words wordList, find all the shortest transformation sequences from startWord to targetWord.

  • Each transformed word must exist in wordList.
  • Only one letter can be changed at a time.
  • Each transformation sequence should be as short as possible.

Return all such sequences in any order.

Examples

Start Target Word List Result Description
hit cog ["hot","dot","dog","lot","log","cog"] [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] Two shortest sequences found
hit cog ["hot","dot","dog","lot","log"] [] cog not in wordList, no transformation
a c ["a","b","c"] [["a","c"]] Direct transformation with one letter change
abc def ["dbc","dec","def"] [["abc","dbc","dec","def"]] Chain with exact path

Solution

Understanding the Problem

We are given three things: a startWord, a targetWord, and a list of allowed words called wordList.

Our task is to transform startWord into targetWord, but under some important rules:

  • We can only change one letter at a time.
  • Each intermediate word formed during transformation must exist in the wordList.
  • We are not just looking for one sequence, but all shortest sequences that complete the transformation.

This is like finding the shortest paths in a word graph, where each node is a word and edges connect words that differ by only one letter.

Step-by-Step Solution with Example

Step 1: Analyze the Example

Let’s take the example:

startWord = "hit"
targetWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

We want to transform "hit" to "cog" using valid intermediate words. Valid paths include: ["hit", "hot", "dot", "dog", "cog"] and ["hit", "hot", "lot", "log", "cog"]. Both have 5 words and are the shortest.

Step 2: Use BFS to Find Levels

We perform Breadth-First Search (BFS) starting from startWord. Why BFS?

  • BFS explores all words level by level — this helps us find the shortest path(s).
  • We build a graph (adjacency list) to remember how each word is connected and from which word it came.
  • We also track the level (or step count) when we reach a word.

Step 3: Stop When Target is Reached

We stop BFS as soon as we reach the targetWord. This ensures we do not explore longer paths than necessary. All words discovered at that level are part of the shortest sequence.

Step 4: Backtrack Using DFS

Once BFS is done, we now backtrack using Depth-First Search (DFS) from the targetWord to startWord, collecting all valid paths:

  • We only move from a word to another word that is one level lower — this keeps the path short.
  • Each path we build represents one valid shortest transformation sequence.

Step 5: Return the Results

All collected paths are stored and returned. Each path shows how we can go from startWord to targetWord using valid transformations.

Edge Cases

  • Target word missing from the word list: If targetWord is not in the wordList, no transformation is possible. We return an empty list.
  • Start word not in list: That’s okay. startWord doesn’t have to be in wordList.
  • No path exists: BFS may complete without ever reaching targetWord. In this case, we also return an empty list.
  • Words of different lengths: All words should be the same length for the one-letter transformation rule to make sense.

Finally

This problem is a combination of graph traversal and path reconstruction. We use BFS to determine the minimum number of steps and build the transformation graph, then DFS to collect all valid shortest paths. The use of two algorithms — BFS followed by DFS — ensures correctness and efficiency.

Understanding the reasoning behind each step — why BFS first, why we backtrack with DFS, and how we prune paths based on levels — helps make this problem clear and approachable even for beginners.

Algorithm Steps

  1. Use BFS starting from startWord to generate a graph and record the level (distance) of each word from the start.
  2. While performing BFS, record edges only between valid transformations (words differing by one letter).
  3. If targetWord is not reachable, return an empty list.
  4. Use DFS or backtracking starting from targetWord and move backwards using the levels map to collect all shortest paths.
  5. Return the collected transformation sequences.

Code

JavaScript
function wordLadderII(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return [];

  const graph = new Map();
  const level = new Map();
  const res = [];

  const bfs = () => {
    const queue = [beginWord];
    level.set(beginWord, 0);

    while (queue.length) {
      const word = queue.shift();
      const currLevel = level.get(word);
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (wordSet.has(next)) {
            if (!level.has(next)) {
              level.set(next, currLevel + 1);
              queue.push(next);
              graph.set(next, [word]);
            } else if (level.get(next) === currLevel + 1) {
              graph.get(next).push(word);
            }
          }
        }
      }
    }
  };

  const dfs = (word, path) => {
    if (word === beginWord) {
      res.push([beginWord, ...path.reverse()]);
      return;
    }
    if (!graph.has(word)) return;
    for (const prev of graph.get(word)) {
      dfs(prev, [...path, word]);
    }
  };

  bfs();
  if (level.has(endWord)) dfs(endWord, []);

  return res;
}

console.log(wordLadderII("hit", "cog", ["hot","dot","dog","lot","log","cog"]));

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n * m^2)Best case occurs when the target word is found early during BFS. Here, n is the number of words in the list, and m is the word length. Checking all possible one-letter transformations involves m changes per word and comparing with up to n words.
Average CaseO(n * m^2)On average, we process each word and generate transformations by changing every character (m positions), resulting in n * m comparisons.
Worst CaseO(n * m^2 + k)In the worst case, BFS explores all words, and backtracking (DFS) finds all possible shortest sequences (let's say k sequences). So the total complexity is O(n * m^2 + k).

Space Complexity

O(n * m + k)

Explanation: We store the graph (adjacency list), the level map, and the sequences found. Graph and level maps use O(n * m), and storing all k shortest sequences adds O(k).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...