Search Word in Trie

To determine whether a word exists in a Trie, we perform a character-by-character traversal starting from the root node. For each character in the search word, we check if the character exists in the current node's children. If it does, we move to that child node and continue. If we encounter a character that doesn't exist in the Trie at any point, we know immediately that the word does not exist, so we return false.

However, reaching the end of the word isn't enough — we must also ensure that the last character leads us to a node that is explicitly marked as the end of a valid word. If not, then the word is only a prefix of some longer word and should still return false.

Let’s consider some cases:

• Normal case:

  If we insert ["one", "only", "once"] and search for "once", we follow each letter until the end and confirm it ends at a valid word node. So, return true. Visualization

• Prefix case:

  Searching for "on" in the same Trie reaches valid characters but doesn’t hit an end-of-word node, so we return false. Visualization
• Empty Trie: If no words are inserted, any search word will return false because the Trie is completely empty.
• Empty string search: Searching with an empty string is often considered invalid unless explicitly allowed. In most Trie implementations, this will return false.

This operation is highly efficient — its time complexity is O(m), where m is the length of the search word, making it much faster than linear search for large sets of words.

1. Start from the root node of the Trie.
2. For each character in the input word:
   1. Check if the character exists in the current node's children map.
   2. If it does, move to the corresponding child node.
   3. If it does not, return false — the word is not present in the Trie.
3. After traversing all characters, check if the current node is marked as the end of a valid word.
4. Return true only if the final node signifies the end of a word; otherwise, return false.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    bool isEndOfWord;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

void insert(TrieNode* root, const char* word) {
    TrieNode* node = root;
    while (*word) {
        int index = *word - 'a';
        if (!node->children[index]) {
            node->children[index] = createNode();
        }
        node = node->children[index];
        word++;
    }
    node->isEndOfWord = true;
}

bool search(TrieNode* root, const char* word) {
    TrieNode* node = root;
    while (*word) {
        int index = *word - 'a';
        if (!node->children[index]) {
            return false;
        }
        node = node->children[index];
        word++;
    }
    return node->isEndOfWord;
}

int main() {
    TrieNode* root = createNode();
    insert(root, "apple");
    insert(root, "app");
    printf("%s\n", search(root, "apple") ? "true" : "false"); // true
    printf("%s\n", search(root, "appl") ? "true" : "false");  // false
    return 0;
}

#include <iostream>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; ++i)
            children[i] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (!node->children[index])
                node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (!node->children[index]) return false;
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    cout << boolalpha << trie.search("apple") << endl; // true
    cout << trie.search("appl") << endl;  // false
    return 0;
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    trie.insert("app")
    print(trie.search("apple"))  # True
    print(trie.search("appl"))   # False

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

public class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("appl"));  // false
    }
}

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

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

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

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

// Example usage:
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.search("apple")); // true
console.log(trie.search("appl"));  // false;

package main

import (
	"fmt"
)

type TrieNode struct {
	children map[rune]*TrieNode
	isEndOfWord bool
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, ch := range word {
		if _, exists := node.children[ch]; !exists {
			node.children[ch] = NewTrieNode()
		}
		node = node.children[ch]
	}
	node.isEndOfWord = true
}

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, ch := range word {
		if _, exists := node.children[ch]; !exists {
			return false
		}
		node = node.children[ch]
	}
	return node.isEndOfWord
}

func main() {
	trie := NewTrie()
	trie.Insert("apple")
	trie.Insert("app")
	fmt.Println(trie.Search("apple")) // true
	fmt.Println(trie.Search("appl"))  // false
}

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert_with(TrieNode::new);
        }
        node.is_end_of_word = true;
    }

    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for ch in word.chars() {
            match node.children.get(&ch) {
                Some(next_node) => node = next_node,
                None => return false,
            }
        }
        node.is_end_of_word
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("apple");
    trie.insert("app");
    println!("{}", trie.search("apple")); // true
    println!("{}", trie.search("appl"));  // false
}

class TrieNode {
    val children = Array<TrieNode?>(26) { null }
    var isEndOfWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (ch in word) {
            val index = ch - 'a'
            if (node.children[index] == null) {
                node.children[index] = TrieNode()
            }
            node = node.children[index]!!
        }
        node.isEndOfWord = true
    }

    fun search(word: String): Boolean {
        var node = root
        for (ch in word) {
            val index = ch - 'a'
            node = node.children[index] ?: return false
        }
        return node.isEndOfWord
    }
}

fun main() {
    val trie = Trie()
    trie.insert("apple")
    trie.insert("app")
    println(trie.search("apple")) // true
    println(trie.search("appl"))  // false
}

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord = false
}

class Trie {
    private let root = TrieNode()

    func insert(_ word: String) {
        var node = root
        for ch in word {
            if node.children[ch] == nil {
                node.children[ch] = TrieNode()
            }
            node = node.children[ch]!
        }
        node.isEndOfWord = true
    }

    func search(_ word: String) -> Bool {
        var node = root
        for ch in word {
            guard let nextNode = node.children[ch] else {
                return false
            }
            node = nextNode
        }
        return node.isEndOfWord
    }
}

let trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("apple")) // true
print(trie.search("appl"))  // false

class TrieNode {
  children: { [key: string]: TrieNode } = {};
  isEndOfWord: boolean = false;
}

class Trie {
  private root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        return false;
      }
      node = node.children[ch];
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.search("apple")); // true
console.log(trie.search("appl"));  // false;

Time complexity

Space complexity

O(1)

The search operation uses only a constant amount of extra space for pointers or references during traversal. No additional data structures are created proportional to input size.