LeetCode 208 Implement Trie - Example and Complexity Analysis

Trace inserting "apple" then "app".

Insert "apple":

• Create nodes: root → a → p → p → l → e
• Mark 'e' as word end.

Insert "app":

• Path a → p → p already exists.
• Mark this 'p' as word end.

Search "apple": follow a → p → p → l → e, is word end? Yes. Return true.

Search "app": follow a → p → p, is word end? Yes. Return true.

Search "ap": follow a → p, is word end? No. Return false.

StartsWith "app": follow a → p → p, path exists? Yes. Return true.

Each operation traverses at most $m$ characters where $m$ is word/prefix length. $O(m)$ time per operation. Space: $O(T)$ where $T$ is total characters across all words.