{"id":1070,"date":"2025-09-01T22:43:12","date_gmt":"2025-09-01T17:13:12","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1070"},"modified":"2025-09-01T22:43:13","modified_gmt":"2025-09-01T17:13:13","slug":"implement-trie-prefix-tree","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/implement-trie-prefix-tree\/","title":{"rendered":"Implement Trie (Prefix Tree) | Leetcode 208 | Efficient String Data Structure"},"content":{"rendered":"\n

The Implement Trie (Prefix Tree)<\/strong> problem asks us to design a Trie data structure that supports the following operations:<\/p>\n\n\n\n

    \n
  1. Insert(word):<\/strong> Insert a word into the Trie.<\/li>\n\n\n\n
  2. Search(word):<\/strong> Return True<\/code> if the word is in the Trie, False<\/code> otherwise.<\/li>\n\n\n\n
  3. startsWith(prefix):<\/strong> Return True<\/code> if there is any word in the Trie that starts with the given prefix.<\/li>\n<\/ol>\n\n\n\n

    A Trie (Prefix Tree)<\/strong> is a tree-like data structure that efficiently stores and retrieves strings, especially useful for prefix-based searches.<\/p>\n\n\n\n

    Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

    \n\n\n\n

    Examples<\/h3>\n\n\n\n

    Example 1<\/strong><\/p>\n\n\n\n

    <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
    Input:<\/span><\/span>\nTrie trie = new Trie()<\/span>;<\/span><\/span>\ntrie.insert(<\/span>"apple"<\/span>)<\/span>;<\/span><\/span>\ntrie.search(<\/span>"apple"<\/span>);   \/\/ returns <\/span>True<\/span><\/span>\ntrie.search(<\/span>"app"<\/span>);     \/\/ returns <\/span>False<\/span><\/span>\ntrie.startsWith(<\/span>"app"<\/span>); \/\/ returns <\/span>True<\/span><\/span>\ntrie.insert(<\/span>"app"<\/span>)<\/span>;<\/span><\/span>\ntrie.search(<\/span>"app"<\/span>);     \/\/ returns <\/span>True<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    \n\n\n\n
    Intuition and Approach<\/h2>\n\n\n\n
    The Trie is built using nodes where:<\/p>\n\n\n\n