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.

Practice

1. What does the search operation in a Trie data structure primarily check for?

easy

A. The length of the longest word in the Trie

B. If the Trie is empty

C. If a given word exists in the Trie

D. The number of words stored in the Trie

Solution

1. Step 1: Understand the purpose of Trie search

   The search operation in a Trie is designed to check if a specific word is present in the Trie by traversing nodes corresponding to each character.

2. Step 2: Identify what the search confirms

   It confirms the presence or absence of the entire word, not the count or length of words stored.

3. Final Answer:

   If a given word exists in the Trie -> Option C

4. Quick Check:

   Trie search checks word existence [OK]

Hint: Search checks full word presence in Trie nodes [OK]

Common Mistakes:

• Confusing search with counting words
• Thinking search returns word length
• Assuming search checks if Trie is empty

2. Which of the following is the correct way to check if a character node exists in a Trie during search in JavaScript?

easy

A. if (node.char !== null)

B. if (node[char] !== undefined)

C. if (node.has(char))

D. if (node.char === true)

Solution

1. Step 1: Understand Trie node structure in JavaScript

   Trie nodes are usually objects where keys are characters. Checking if a character exists uses property access and undefined check.

2. Step 2: Identify correct syntax for existence check

   Using node[char] !== undefined correctly checks if the character key exists in the node object.

3. Final Answer:

   if (node[char] !== undefined) -> Option B

4. Quick Check:

   Check node property with !== undefined [OK]

Hint: Use node[char] !== undefined to check character node [OK]

Common Mistakes:

• Using dot notation with variable char
• Using incorrect method like has() on object
• Checking for null instead of undefined

3. What will be the output of the following JavaScript code snippet?

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
console.log(trie.search('cat'));
console.log(trie.search('cap'));

medium

A. true false

B. false true

C. true true

D. false false

Solution

1. Step 1: Insert words 'cat' and 'car' into Trie

   Both words are inserted by creating nodes for each character and marking the last node's isEnd as true.

2. Step 2: Search for 'cat' and 'cap'

   'cat' exists fully with isEnd true, so search returns true. 'cap' is missing 'p' node, so search returns false.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   Search 'cat' = true, 'cap' = false [OK]

Hint: Search returns true only if full word and isEnd true [OK]

Common Mistakes:

• Assuming partial matches return true
• Not setting isEnd flag on insert
• Confusing children object access

4. Identify the bug in the following Trie search method and select the correct fix:

search(word) {
  let node = this.root;
  for (const char of word) {
    if (node.children[char] === undefined) return false;
    node = node.children[char];
  }
  return true;
}

medium

A. Use 'for (let i=0; i

B. Change '===' to '!==' in the if condition

C. Initialize node with a new TrieNode inside the method

D. Return node.isEnd instead of true at the end

Solution

1. Step 1: Analyze the search method's return value

   The method returns true after traversing all characters without checking if the last node marks the end of a word.

2. Step 2: Correct the return to check word completion

   Return node.isEnd to confirm the word ends here, not just prefix exists.

3. Final Answer:

   Return node.isEnd instead of true at the end -> Option D

4. Quick Check:

   Check isEnd flag to confirm full word [OK]

Hint: Always check isEnd flag after traversal [OK]

Common Mistakes:

• Returning true without isEnd check
• Changing comparison operator incorrectly
• Unnecessary loop syntax changes

5. Given a Trie containing the words ['apple', 'app', 'bat', 'bath'], which of the following search queries will return true? Assume the search method correctly checks for full word presence. Select the correct combination.

hard

A. search('app'), search('bat'), search('bath')

B. search('appl'), search('bat'), search('bath')

C. search('apple'), search('bat'), search('batman')

D. search('app'), search('bath'), search('batman')

Solution

1. Step 1: Identify words present in the Trie

   The Trie contains 'apple', 'app', 'bat', and 'bath'. Only these exact words return true on search.

2. Step 2: Check each option's search queries

   search('app'), search('bat'), search('bath') searches 'app', 'bat', 'bath' all present. Others include partial or missing words like 'appl' or 'batman' which return false.

3. Final Answer:

   search('app'), search('bat'), search('bath') -> Option A

4. Quick Check:

   Only full words in Trie return true [OK]

Hint: Search true only for full words inserted in Trie [OK]

Common Mistakes:

• Assuming partial words return true
• Confusing prefixes with full words
• Including words not inserted in Trie