Coding Interview: Implement a Radix Tree for Prefix Routing

Prompt and context

You are given string keys such as /api, /api/users, and /api/users/admin. Implement a radix tree in which each edge stores a non-empty string and each node may hold a value. Support insert(key, value), get(key), longestPrefix(key), and delete(key). Empty keys are allowed only as the root value. The interviewer wants the data structure and reasoning, not a library call.

What the interviewer is assessing

• Do you maintain the invariant that every non-root edge label is non-empty and siblings have different first characters?
• Can you split an edge at the first mismatch without losing either subtree or value?
• Can you distinguish exact lookup from longest-prefix lookup?
• Do you compress unary non-value nodes after deletion and state the real complexity in key length?

Clarifying questions to ask

Ask whether keys are bytes or Unicode code points, whether matching is case-sensitive, whether duplicate inserts replace values, and whether concurrent access is required. Ask whether longestPrefix returns the matched key, value, or both. A byte-oriented implementation is simplest and makes complexity depend on bytes; Unicode normalization belongs outside the tree unless explicitly required. If concurrency is required, add synchronization around the structure rather than silently claiming the algorithm is thread-safe.

A 30-second answer framework

Each node stores an edge label, an optional value, and children indexed by their first byte. During insertion, compare the remaining key with the child label. If they fully match, descend; if they partially match, split the child into a common-prefix node and two suffix nodes. Exact lookup succeeds only when the whole key is consumed at a value node. Longest-prefix lookup remembers the deepest value seen while descending. Deletion clears a value and merges a node with its sole child when the node has no value.

Step-by-step deep dive

1. State the invariant. The root has no edge label. Every other node has a non-empty label. No two children of one node start with the same byte. A node can store a value even when it also has children, so /api and /api/users coexist.
2. Insert by longest common prefix. Let p be the common prefix between the remaining key and a child label. If p is empty, choose another child. If p equals the child label, consume it and recurse. If p is shorter, create a new parent labelled p, move the old child under its suffix, then attach the new key suffix or replace the value when the key ends at the split.
3. Lookup. Exact lookup consumes one edge at a time and fails on a mismatch or missing child. For longest-prefix lookup, record the root value first, then record every value node reached before the key ends; return the last record.
4. Delete and compress. Clear the value at the target. If the node has no value and one child, concatenate the two labels and promote the child’s children. If it has multiple children or still has a value, keep the node. This preserves the sibling invariant.
5. Complexity. With child selection by a hash map, each operation compares at most the input key bytes, so time is O(k) plus hash-map overhead and space is O(total stored key bytes). Path compression reduces sparse unary nodes; it does not make a long key constant-time.
6. Test adversarial cases. Test empty and single-character keys, inserting a key that is a prefix of an existing key, inserting a key that extends an existing key, splitting in the middle of an edge, duplicate replacement, deleting a leaf, deleting a prefix value, deleting the only key, and longest-prefix queries with no match.

High-quality sample answer

I would represent an edge as a non-empty byte string and keep children by their first byte. The only nontrivial operation is insertion: compare the child label with the remaining key, and split at the first mismatch. That split creates a common-prefix node, keeps the old suffix and subtree, and attaches the new suffix. Lookup follows complete labels; longest-prefix lookup remembers the deepest node that owns a value. Deletion clears the value and merges a value-less node with its only child. Here is the core split shape in Go-like pseudocode:

type node struct {
    label string
    value any
    hasValue bool
    child map[byte]*node
}

// When common is shorter than child.label:
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}

In production code I would handle the case where newSuffix is empty by storing the value on parent, and I would make deletion merge only when hasValue is false and there is exactly one child. I would test the invariant after every mutation, not just assert that example lookups pass.

Common mistakes

• Treating a radix tree as one-character trie nodes → path compression is lost → store non-empty edge labels and compare the whole label.
• Splitting an edge but dropping its old value or children → existing keys disappear → move the old node under its suffix before attaching the new suffix.
• Returning the first matching value for longest-prefix lookup → a more specific route loses → keep updating the candidate at every value node.
• Merging a node that still owns a value → a shorter key is deleted accidentally → merge only value-less unary nodes.
• Claiming O(1) lookup → the key still must be compared → state O(k) in key length and explain child-map costs.

Follow-up questions and answers

What changes if keys are case-insensitive?

Normalize keys before insertion and lookup using one documented rule, such as ASCII lowercase. Do not normalize only during lookup; otherwise two spellings can occupy inconsistent paths. Unicode case folding and normalization should be a separate, specified policy.

How would you support wildcard route segments?

Add an explicit precedence rule, for example static edge before parameter edge before catch-all edge. The radix invariant still handles literal prefixes, but matching becomes a search over edge kinds, so state the maximum number of wildcard branches and test ambiguous routes.

Can the tree be made safe for concurrent reads and writes?

Use a read-write lock or copy-on-write snapshots. A lock-free claim needs a memory-reclamation design; simply using an atomic root does not make in-place splits and merges safe. Keep the algorithmic invariant and synchronization policy separate.