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 characters where is word/prefix length. time per operation. Space: where is total characters across all words.