Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in JavaScript

Solution: Find All Words Stored in Trie

Understand how to implement a function that finds all words stored in a trie data structure through recursive traversal. Explore depth-first search methods to extract words, manage node exploration, and analyze time and space complexity for efficient code.

We'll cover the following...

Statement

Given a trie data structure representing a list of words, implement a function that finds and returns all words stored in the trie.

Constraints:

  • 0≤0\leq words.length ≤103\leq 10^3

  • 1≤ 1\leq words[i].length ≤102\leq10^2

  • All words[i] consist of lowercase English letters.

Solution

This solution utilizes a trie data structure, efficiently organizing a list of words. In a trie, each word is broken down into letters, each represented by a node in the trie. Starting from the root node, each subsequent letter in the word corresponds to a child node of the previous letter’s node. This process continues until the entire word is represented by a path from the root node to a node marked as the end of the word. The algorithm explores each node by recursively traversing the trie from the root node, effectively enumerating all possible character combinations that form valid words. At each node, it checks if it marks the end of a word, constructing the word by accumulating characters from the word array. This recursive exploration continues until all words in the trie are found and stored in the result list. Let’s look at how each function behaves and contributes to this approach:

  • The getMaxDepth function recursively determines the maximum depth of a tree. It starts from a given root node and traverses through the tree’s children, incrementing the level by one each time. This recursive traversal continues until it reaches the leaf nodes. At each level, the function compares the current depth with the maximum depth encountered so far, updating the maximum depth if necessary.

  • The findWords function recursively retrieves words from a tree structure. It initializes an empty list to store words and a list with a size determined by the tree’s maximum depth. As it traverses the tree, it retrieves the characters at each level to form words, appending them to the result list when a word is complete. Finally, it returns the list of extracted words.

  • The getWords function utilizes a depth-first search (DFS) approach to traverse a trie data structure. It starts from the given root node and recursively explores each branch. At each node, the algorithm checks if it marks the end of a word. If it does, it constructs the word by concatenating characters stored in the word array to the current level and adds it to the result list. Then, the algorithm iterates over the current node’s children, representing possible next characters in the words. For each child, it updates the word array with the character at the current level and recursively explores the child node. This process continues until all possible paths in the trie are explored, generating all words stored in the trie.

Let’s look at the illustration below to better understand the solution:

canvasAnimation-image
1 / 16

Let’s look at the code for this solution below:

Javascript (babel-node-es2024)
"use strict";
import {Trie} from './Trie.js';
// Recursive function to get the maximum depth of a trie
function getMaxDepth(root, level) {
	// If the root is null, return the current level
    if (root === null) {
        return level;
    }
    let maxDepth = level;
    for (let child of root.children) {
        if (child !== null) {
			// Recursively calculate the maximum depth of the subtree
            maxDepth = Math.max(maxDepth, getMaxDepth(child, level + 1));
        }
    }
    return maxDepth;
}
// Recursive function to find all the words stored in a trie
function getWords(root, result, level, string) {
	// If the current node marks the end of a word, construct the word and append it to the result list
	if (root.isEndWord) {
		let temp = "";
		for (var x = 0; x < level; x++) {
			temp += String(string[x]);
		}
		result.push(temp);
	}
	for (var i = 0; i < 26; i++) {
		if (root.children[i] != null) {
			// Update the word array with the character at the current level
			string[level] = String.fromCharCode(i + "a".charCodeAt(0));
			
			// Recursively explore the child node
			getWords(root.children[i], result, level + 1, string);
		}
	}
}
// Helper function to call the getWords function
function findWords(root) {
	let result = [];
	let chararr = [];
	let size = getMaxDepth(root, 0);
	for (var i = 0; i < size; i++) {
		chararr.push(null);
	}
	getWords(root, result, 0, chararr);
	return result;
}
// Driver Code
let num = 1
let words = [
	["gram", "groom", "ace", "act", "actor"],
	["abs", "crow", "crop", "abstain", "crunch"],
	["dorm", "norm", "prom", "loom", "room"],
	["prey", "prep", "press", "preps", "prefix"],
	["moon", "once", "face", "dice", "mole"]
];
for (let wordList of words) {
	let t = new Trie();
	for (let w of wordList) {
		console.log(`Insert word: '${w}'`);
		t.insert(w);
		++num;
	}
	let wordsFound = findWords(t.root);
	console.log("\nWords found: [" + wordsFound.map(word => `'${word}'`).join(' ') + "]");
	console.log("-".repeat(100));
}

Complexity analysis

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the total number of characters in all words stored in the trie. This complexity arises from traversing each trie node once to retrieve the words.

Space complexity

The space complexity of the provided code is O(n+m)O(n + m), where nn is the total number of characters in all words stored in the trie, and mm is the length of the longest word.