Trie Search Operation in DSA Javascript - Build from Scratch

Trie Search Operation

📖 Scenario: Imagine you are building a simple search feature for a phone contact list. You want to quickly check if a contact name exists in your list.

🎯 Goal: You will build a small Trie (prefix tree) structure and write code to search if a given contact name is present in it.

📋 What You'll Learn

Create a Trie node structure using JavaScript objects

Insert a few contact names into the Trie

Write a search function to check if a contact name exists

Print the search result as true or false

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words or prefixes.

💼 Career

Understanding Trie search operations helps in roles involving text processing, search optimization, and building efficient data retrieval systems.

1

Create the Trie data structure with contact names

Create a variable called trie as an empty object. Then insert these exact contact names into the trie: "anna", "anne", "bob", "bobby". Use nested objects to represent each letter node. Mark the end of a word by setting a property isEnd to true at the last letter node.

DSA Javascript

const trie = {};
// Your code here to insert "anna", "anne", "bob", "bobby" into trie

Hint

Use a function to add each word letter by letter into the trie object. Mark the end of each word with isEnd = true.

2

Create a variable for the search word

Create a variable called searchWord and set it to the string "bob".

DSA Javascript

const trie = {};

function insert(word) {
  let node = trie;
  for (const char of word) {
    if (!node[char]) {
      node[char] = {};
    }
    node = node[char];
  }
  node.isEnd = true;
}

insert("anna");
insert("anne");
insert("bob");
insert("bobby");

// Create a variable searchWord and set it to "bob"
// Your code here

Hint

Just create a variable named searchWord and assign it the string "bob".

3

Write the search function to check if the word exists in the trie

Write a function called search that takes a parameter word. Use a variable node starting at trie. Loop through each character in word. If the character is not found in node, return false. Otherwise, move node to that character's child. After the loop, return true only if node.isEnd is true, else false. Then call search(searchWord) and store the result in a variable called result.

DSA Javascript

const trie = {};

function insert(word) {
  let node = trie;
  for (const char of word) {
    if (!node[char]) {
      node[char] = {};
    }
    node = node[char];
  }
  node.isEnd = true;
}

insert("anna");
insert("anne");
insert("bob");
insert("bobby");

const searchWord = "bob";

// Write function search(word) and call it with searchWord
// Store the result in variable result
// Your code here

Hint

Check each letter in the trie. If missing, return false. If all letters found, return true only if isEnd is true.

4

Print the search result

Write a console.log statement to print the value of the variable result.

DSA Javascript

const trie = {};

function insert(word) {
  let node = trie;
  for (const char of word) {
    if (!node[char]) {
      node[char] = {};
    }
    node = node[char];
  }
  node.isEnd = true;
}

insert("anna");
insert("anne");
insert("bob");
insert("bobby");

const searchWord = "bob";

function search(word) {
  let node = trie;
  for (const char of word) {
    if (!node[char]) {
      return false;
    }
    node = node[char];
  }
  return node.isEnd === true;
}

const result = search(searchWord);

// Print the result variable
// Your code here

Hint

Use console.log(result) to show if the word was found.