Prefix Search in Trie

To solve the problem of Prefix Search in Trie, we need to determine if any word stored in the Trie starts with a given prefix. This is different from a full word search because we only care whether a word starts with the prefix — not whether a word matches the prefix entirely.

How we approach the problem

A Trie is a tree-like data structure that is particularly efficient for prefix-based queries. Each node in the Trie represents a character, and a path from the root to any node represents a prefix of some word(s).

When performing a prefix search:

• We start from the root of the Trie.
• We go through each character of the prefix one by one.
• For each character, we check whether it exists as a child of the current node.
• If any character is missing, we conclude that no word with that prefix exists in the Trie.
• If we reach the end of the prefix successfully, it means at least one word in the Trie starts with the prefix.

Example:

Suppose the Trie contains: ["app", "apple", "bat", "ball"]

• Prefix to search: "ap"
• Start at root → Check for 'a' → Exists
• Move to 'a' → Check for 'p' → Exists
• All characters in the prefix found → Return true

Edge Cases

Case 1 - Empty prefix string

Description: The prefix string is an empty string: ""

• Since every word starts with an empty prefix, we should return true.

Example:

Trie: ["a", "ab", "abc"]
Prefix: "" → Result: true

Case 2 - Prefix longer than any stored word

Description: The prefix is longer than any word in the Trie.

• Traverse the Trie character by character.
• If at any point the character is not found, return false.

Example:

Trie: ["do", "dog", "dot"]
Prefix: "dodge" → Result: false

For char 'o', there is no child 'd'. Prefix not present in the trie, hence returning false.

Case 3 - Prefix partially matches a word

Description: The prefix matches the start of a word but does not reach a full word.

• We only care if the prefix matches a path in the Trie.
• If the prefix exists in the Trie path, return true.

Example:

Trie: ["go", "gone", "golf"]
Prefix: "gol" → Result: true

Case 4 - Prefix not found at all

Description: The prefix has no matching characters in the Trie.

• As soon as we find a character in the prefix that is not in the current node’s children, we return false.

Example:

Trie: ["cat", "car", "cart"]
Prefix: "dog" → Result: false

Root of the trie has only one child 'c'. First character in given prefix is 'd' and this is not there in the list of children of the root of trie. Therefore, return false.

Case 5 - Multiple words start with the same prefix

Description: The prefix matches the beginning of several words.

• Even if one word starts with the prefix, return true.
• Don’t worry about counting how many words — just whether any word matches.

Example:

Trie: ["star", "start", "stark"]
Prefix: "sta" → Result: true

Case 6 - Trie is empty

Description: No words are present in the Trie at all.

• If Trie is empty, any prefix will return false.

Example:

Trie: []
Prefix: "a" → Result: false

1. Start from the root node of the Trie.
2. For each character in the input prefix:
   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 — no word in the Trie starts with this prefix.
3. After traversing all characters, return true — at least one word in the Trie starts with the given prefix.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.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;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (!node->children[index])
            node->children[index] = createNode();
        node = node->children[index];
    }
    node->isEndOfWord = true;
}

bool startsWith(TrieNode* root, const char* prefix) {
    TrieNode* node = root;
    for (int i = 0; prefix[i]; i++) {
        int index = prefix[i] - 'a';
        if (!node->children[index])
            return false;
        node = node->children[index];
    }
    return true;
}

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

#include <iostream>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode() : isEndOfWord(false) {}
};

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

    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (!node->children.count(ch))
                return false;
            node = node->children[ch];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    cout << boolalpha << trie.startsWith("app") << endl; // true
    cout << trie.startsWith("apx") << 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 startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

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

import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<>();
    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()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEndOfWord = true;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return true;
    }

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

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = 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.isEndOfWord = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

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

package main

import "fmt"

const alphabetSize = 26

type TrieNode struct {
    children [alphabetSize]*TrieNode
    isEndOfWord bool
}

type Trie struct {
    root *TrieNode
}

func newTrieNode() *TrieNode {
    return &TrieNode{}
}

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

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            node.children[index] = newTrieNode()
        }
        node = node.children[index]
    }
    node.isEndOfWord = true
}

func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        index := ch - 'a'
        if node.children[index] == nil {
            return false
        }
        node = node.children[index]
    }
    return true
}

func main() {
    trie := NewTrie()
    trie.Insert("apple")
    trie.Insert("app")
    fmt.Println(trie.StartsWith("app")) // true
    fmt.Println(trie.StartsWith("apx")) // 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 starts_with(&self, prefix: &str) -> bool {
        let mut node = &self.root;
        for ch in prefix.chars() {
            if let Some(next_node) = node.children.get(&ch) {
                node = next_node;
            } else {
                return false;
            }
        }
        true
    }
}

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

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var isEndOfWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (ch in word) {
            node = node.children.getOrPut(ch) { TrieNode() }
        }
        node.isEndOfWord = true
    }

    fun startsWith(prefix: String): Boolean {
        var node = root
        for (ch in prefix) {
            node = node.children[ch] ?: return false
        }
        return true
    }
}

fun main() {
    val trie = Trie()
    trie.insert("apple")
    trie.insert("app")
    println(trie.startsWith("app"))  // true
    println(trie.startsWith("apx"))  // 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 startsWith(_ prefix: String) -> Bool {
        var node = root
        for ch in prefix {
            guard let nextNode = node.children[ch] else {
                return false
            }
            node = nextNode
        }
        return true
    }
}

let trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.startsWith("app"))  // true
print(trie.startsWith("apx"))  // false

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

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

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

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

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

Time complexity

Space complexity

O(1)

The search uses a constant amount of extra space (just a pointer to traverse the Trie), as no additional data structures are created during traversal.