Review: Trie Tree Problems Posted on January 22, 2018October 4, 2019 by braindenny Trie tree is good at prefix-searching requirements. Key operations: insert, search, prefix, getHeight, etc. Basic Abstractions Name Summary children map[byte]*Trie Use pointer Common Trie operations Insert/Search/StartsWith Sometimes no need to track isLeaf Leetcode: Word Squares Trie for inverted index Leetcode: Stream of Characters Scenarios type Trie struct { children map[byte]*Trie isLeaf bool } Code Skeleton Questions Name Example Extra datastructure in trie can save time and simplify code Leetcode: Word Search II For a-z, use children [26]*Trie vs map[byte]*Trie Leetcode: Word Search II The most impressive problems to trie problem Leetcode: Maximum XOR of Two Numbers in an Array. Time complexity of trie problems? Time O(w)/O(n*w), Space O(w) trie vs hashmap Leetcode: Word Break II Solution: trie with extra datastructure in leaf nodes // https://code.dennyzhang.com/word-search-ii type Trie struct { children map[byte]*Trie isLeaf bool index int } CheatSheet: Leetcode For Code Interview See all trie tree problems: #trie Review: Trie Tree ProblemsLeetcode: Word Search IILeetcode: Stream of CharactersLeetcode: Short Encoding of WordsLeetcode: Replace WordsLeetcode: Remove Sub-Folders from the FilesystemLeetcode: Prefix and Suffix SearchLeetcode: Maximum XOR of Two Numbers in an ArrayLeetcode: Map Sum PairsLeetcode: Longest Word in DictionaryLeetcode: Implement Trie (Prefix Tree)Leetcode: Implement Magic DictionaryLeetcode: Add and Search Word – Data structure design See more blog_posts. Post Views: 11