208. Implement Trie (Prefix Tree)

Q: Map or Array for children at Atlassian?

Map is the more defensible answer because it generalizes to Unicode and arbitrary alphabets. Array is faster for the lowercase-only test set. Mention both and pick Map by default — Atlassian's 'extensibility' rubric explicitly rewards this choice.

Q: Why does the _walk helper matter?

Because search and startsWith differ ONLY in whether you check isEnd at the end. Without _walk you have two near-identical 5-line loops, which is exactly the duplication code-review tools flag. Atlassian's rubric explicitly scores this.

mediumAsked at Atlassian

Implement Trie is an Atlassian-favorite OOP-design problem because tries power Confluence's @-mention autocomplete and Jira's smart label search. You design a prefix tree supporting insert, search (full word), and startsWith (prefix). The grading focus is clean class structure and pointer ownership.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

Glassdoor (2026-Q1)— Atlassian onsite reports cite Implement Trie as a recurring data-structure-design question, especially for SWE-III / Senior loops.
Blind (2025-09)— Atlassian threads describe Trie as 'the autocomplete question' and the natural lead-in to Add and Search Words.

Problem

A trie (pronounced 'try') or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class: Trie() initializes the trie object. void insert(String word) inserts the string word into the trie. boolean search(String word) returns true if the string word is in the trie (was previously inserted). boolean startsWith(String prefix) returns true if there is a previously inserted string with the given prefix.

Constraints

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total to insert, search, and startsWith.

Examples

Example 1

Input

Trie(); insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")

Output

[null,null,true,false,true,null,true]

Approaches

1. Hash-set of all prefixes (brute)

On insert, add every prefix of the word to one set and the full word to another. search checks the words set; startsWith checks the prefix set.

Time: O(L) per op where L is word length
Space: O(N * L)

class TrieBrute {
  constructor() {
    this.words = new Set();
    this.prefixes = new Set();
  }
  insert(word) {
    this.words.add(word);
    for (let i = 1; i <= word.length; i++) this.prefixes.add(word.slice(0, i));
  }
  search(word) { return this.words.has(word); }
  startsWith(prefix) { return this.prefixes.has(prefix); }
}

Tradeoff: Passes the LeetCode judge — but wastes memory because each char is stored in many separate prefix strings. Use it only to motivate the canonical trie. Atlassian will probe whether you can do better.

2. Canonical trie with children object + isEnd flag

Each node has a children map (or fixed-size array for 26 lowercase letters) and an isEnd boolean. insert walks/creates nodes; search walks and checks isEnd; startsWith walks without checking isEnd.

Time: O(L) per op
Space: O(total characters)

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}
class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }
  _walk(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Linear in the word length, no prefix duplication. The shared _walk helper avoids the search/startsWith duplication that many candidates ship as separate near-identical methods — Atlassian explicitly grades 'extracts shared traversal' on this question.

3. Array-of-26 children (memory-tight variant)

Replace the Map with a fixed Array(26) indexed by ch.charCodeAt(0) - 97. Same semantics; constant factor faster, slightly more memory per node.

Time: O(L) per op
Space: O(total characters * 26)

class TrieNodeArr {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}
class TrieArr {
  constructor() {
    this.root = new TrieNodeArr();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) node.children[idx] = new TrieNodeArr();
      node = node.children[idx];
    }
    node.isEnd = true;
  }
  _walk(s) {
    let node = this.root;
    for (const ch of s) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) return null;
      node = node.children[idx];
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Faster constants for the lowercase-only LeetCode constraint. Doesn't generalize to Unicode without switching back to Map. Atlassian interviewers ask 'what would change if input were Unicode?' to test exactly this; have the answer ready.

Atlassian-specific tips

Atlassian's coding rubric scores 'extracts shared traversal helper' on this problem. Write a private _walk method that both search and startsWith call. Without it your code duplicates the for-loop twice, which is the #1 cosmetic complaint on this question in Atlassian onsite reports. Be ready for the immediate follow-up: Add and Search Words (LeetCode 211) with the '.' wildcard, which forces _walk to become a DFS.

Common mistakes

Returning true from search just because the prefix path exists — forgetting the isEnd check.
Conflating the trie root with a child node — root must not be marked isEnd even after inserting an empty string (most LeetCode test sets don't insert empty, but the bug shows up if you do).
Using a 26-array unconditionally without asking about the character set — at uppercase + lowercase you need 52, plus digits = 62.

Follow-up questions

An interviewer at Atlassian may pivot to one of these next:

Add and Search Words Data Structure (LeetCode 211) — extend search to support '.' as wildcard. Forces DFS in _walk.
Word Search II (LeetCode 212) — given a 2D board, find all words from a dictionary; bigram-trie + DFS over the board.
Longest Word in Dictionary (LeetCode 720) — return the longest word that can be built one character at a time from other words in the trie.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Map or Array for children at Atlassian?

Map is the more defensible answer because it generalizes to Unicode and arbitrary alphabets. Array is faster for the lowercase-only test set. Mention both and pick Map by default — Atlassian's 'extensibility' rubric explicitly rewards this choice.

Why does the _walk helper matter?

Because search and startsWith differ ONLY in whether you check isEnd at the end. Without _walk you have two near-identical 5-line loops, which is exactly the duplication code-review tools flag. Atlassian's rubric explicitly scores this.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Implement Trie (Prefix Tree) and other Atlassian interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →