Implement startsWith (prefix search) on a Trie

Question

Accepted Answer

Approach Same walk as search but do not require isEnd at the end. Return false if any character child is missing. Java Solution public boolean startsWith(TrieNode root, String prefix) { TrieNode node = root; for (char c : prefix.toCharArray()) { node = node.children.get(c); if (node == null) return false; } return true; } Complexity Time O(L) Space O(1) extra Interview tip: Autocomplete UIs call startsWith on every keystroke — keep nodes compact.