beingsde
Sign In
Back to all DSA patterns
Trie•Pattern: Trie•Medium

Implement a Trie (Prefix Tree)

Problem Intuition & Objective

Design a Trie with insert, search, and startsWith operations.

Time ComplexityO(L) per op (L = word length)
Optimal
Space ComplexityO(ALPHABET_SIZE × total_chars)
Memory Bounds
Optimal Algorithmic Approach

Array-of-26 children per node for lowercase English letters; HashMap for arbitrary chars.

Core Invariants & Edge Cases

  • Each node has a children array (or HashMap) and an isEnd flag
  • insert traverses/creates nodes for each character
  • search requires reaching a node with isEnd=true; startsWith just requires reaching the last char node
Previous ProblemDiameter of a binary treeNext Problem Word Search in a 2D grid

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.