PATRICIA Trie / Radix Tree — Interview Preparation¶

Audience: Engineers preparing for technical interviews. Tiered questions (Junior → Middle → Senior → Professional) with focused expected answers, followed by a full coding challenge — a radix tree with insert/search plus longest-prefix match — in Go, Java, and Python.

The radix tree is a high-signal topic: it shows you understand the trie family, memory trade-offs, and the IP-routing problem that drives real systems. Many "trie" interview questions are better answered with a radix tree, and senior interviews probe ART and longest-prefix match directly.

Junior Questions (What / How)¶

Middle Questions (Why / When)¶

Senior Questions (Systems / Scale)¶

Professional Questions (Proofs / Analysis)¶

Rapid-Fire Conceptual Questions¶

These are quick "do you really understand it" checks an interviewer mixes in.

Debugging Deep-Dive: "My inserted key isn't found"¶

A frequent interview/live-coding scenario. A candidate inserts ["test", "team"], then search("test") returns false. Walk the diagnosis:

1. Check commonPrefixLen. The classic bug: looping while i <= min(...) (off-by-one) or comparing the wrong indices. "test" and "team" share "te"; cpl must return exactly 2. If it returns 3, the split point is wrong and "test"'s suffix becomes corrupted.
2. Check the split's terminal flag. After splitting "test" at "te", the node spelling "test" (now the "st" child) must keep isEnd = true. If the code moves isEnd to the wrong node, search("test") lands on a non-terminal node.
3. Check search's mid-edge handling. search must return false only when an edge diverges; if it wrongly returns false when an edge fully matches but is the last one, every multi-edge key fails. The condition is cpl < len(child.label) ⇒ fail, then consume cpl and continue.
4. Check children keying. Children keyed by first character must be re-keyed after a split: the old child's first character changed from 't' (of "test") to 's' (of "st"). Forgetting to re-key the split's child under the new first character orphans the subtree.

The fix in 90% of these cases is the split logic. The interviewer is testing whether you can reason about the invariant (labels concatenate to the path) rather than print-debug blindly.

Coding Challenge (3 Languages)¶

Challenge: Radix Tree with Insert, Search, and Longest-Prefix Match¶

Implement a byte/character radix tree supporting: - insert(key) — with correct edge splitting. - search(key) — exact membership. - longestPrefix(key) — the longest stored key that is a prefix of key (the IP-routing operation).

All operations must be O(L). Children are keyed by the first character of each edge label.

Example:

insert("10")          // 10.0.0.0/8
insert("1010")        // 10.10.x.x style longer prefix
insert("")            // default route
longestPrefix("10101") -> "1010"
longestPrefix("1099")  -> "10"
longestPrefix("9")     -> ""      (default route)
search("10")           -> true
search("101")          -> false

Go¶

package main

import "fmt"

type rnode struct {
    label    string
    children map[byte]*rnode
    isEnd    bool
}

type Radix struct{ root *rnode }

func NewRadix() *Radix { return &Radix{root: &rnode{children: map[byte]*rnode{}}} }

func cpl(a, b string) int {
    n := len(a)
    if len(b) < n {
        n = len(b)
    }
    i := 0
    for i < n && a[i] == b[i] {
        i++
    }
    return i
}

func (t *Radix) Insert(key string) {
    n := t.root
    for {
        if key == "" {
            n.isEnd = true
            return
        }
        child, ok := n.children[key[0]]
        if !ok {
            n.children[key[0]] = &rnode{label: key, isEnd: true, children: map[byte]*rnode{}}
            return
        }
        k := cpl(child.label, key)
        if k == len(child.label) {
            key = key[k:]
            n = child
            continue
        }
        split := &rnode{label: child.label[:k], children: map[byte]*rnode{}}
        child.label = child.label[k:]
        split.children[child.label[0]] = child
        n.children[key[0]] = split
        if k == len(key) {
            split.isEnd = true
        } else {
            rest := key[k:]
            split.children[rest[0]] = &rnode{label: rest, isEnd: true, children: map[byte]*rnode{}}
        }
        return
    }
}

func (t *Radix) Search(key string) bool {
    n := t.root
    for key != "" {
        child, ok := n.children[key[0]]
        if !ok {
            return false
        }
        k := cpl(child.label, key)
        if k < len(child.label) {
            return false
        }
        key = key[k:]
        n = child
    }
    return n.isEnd
}

func (t *Radix) LongestPrefix(key string) (string, bool) {
    n := t.root
    best, ok := "", false
    spelled := ""
    for {
        if n.isEnd {
            best, ok = spelled, true
        }
        if key == "" {
            break
        }
        child, present := n.children[key[0]]
        if !present {
            break
        }
        k := cpl(child.label, key)
        if k < len(child.label) {
            break
        }
        spelled += child.label
        key = key[k:]
        n = child
    }
    return best, ok
}

func main() {
    t := NewRadix()
    for _, k := range []string{"10", "1010", ""} {
        t.Insert(k)
    }
    p, _ := t.LongestPrefix("10101")
    fmt.Printf("%q\n", p) // "1010"
    p, _ = t.LongestPrefix("1099")
    fmt.Printf("%q\n", p) // "10"
    p, _ = t.LongestPrefix("9")
    fmt.Printf("%q\n", p) // ""
    fmt.Println(t.Search("10"))  // true
    fmt.Println(t.Search("101")) // false
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class Solution {
    static final class Node {
        String label;
        Map<Character, Node> children = new HashMap<>();
        boolean isEnd;
        Node(String l) { label = l; }
    }

    private final Node root = new Node("");

    static int cpl(String a, String b) {
        int n = Math.min(a.length(), b.length()), i = 0;
        while (i < n && a.charAt(i) == b.charAt(i)) i++;
        return i;
    }

    void insert(String key) {
        Node n = root;
        while (true) {
            if (key.isEmpty()) { n.isEnd = true; return; }
            Node child = n.children.get(key.charAt(0));
            if (child == null) {
                Node leaf = new Node(key); leaf.isEnd = true;
                n.children.put(key.charAt(0), leaf); return;
            }
            int k = cpl(child.label, key);
            if (k == child.label.length()) { key = key.substring(k); n = child; continue; }
            Node split = new Node(child.label.substring(0, k));
            child.label = child.label.substring(k);
            split.children.put(child.label.charAt(0), child);
            n.children.put(key.charAt(0), split);
            if (k == key.length()) split.isEnd = true;
            else {
                String rest = key.substring(k);
                Node leaf = new Node(rest); leaf.isEnd = true;
                split.children.put(rest.charAt(0), leaf);
            }
            return;
        }
    }

    boolean search(String key) {
        Node n = root;
        while (!key.isEmpty()) {
            Node child = n.children.get(key.charAt(0));
            if (child == null) return false;
            int k = cpl(child.label, key);
            if (k < child.label.length()) return false;
            key = key.substring(k); n = child;
        }
        return n.isEnd;
    }

    String longestPrefix(String key) {
        Node n = root; String best = null, spelled = "";
        while (true) {
            if (n.isEnd) best = spelled;
            if (key.isEmpty()) break;
            Node child = n.children.get(key.charAt(0));
            if (child == null) break;
            int k = cpl(child.label, key);
            if (k < child.label.length()) break;
            spelled += child.label; key = key.substring(k); n = child;
        }
        return best;
    }

    public static void main(String[] args) {
        Solution t = new Solution();
        t.insert("10"); t.insert("1010"); t.insert("");
        System.out.println(t.longestPrefix("10101")); // 1010
        System.out.println(t.longestPrefix("1099"));  // 10
        System.out.println(t.longestPrefix("9"));      // (empty string)
        System.out.println(t.search("10"));            // true
        System.out.println(t.search("101"));           // false
    }
}

Python¶

class _Node:
    __slots__ = ("label", "children", "is_end")
    def __init__(self, label=""):
        self.label, self.children, self.is_end = label, {}, False


def _cpl(a, b):
    n = min(len(a), len(b)); i = 0
    while i < n and a[i] == b[i]:
        i += 1
    return i


class Radix:
    def __init__(self):
        self.root = _Node("")

    def insert(self, key):
        n = self.root
        while True:
            if key == "":
                n.is_end = True; return
            child = n.children.get(key[0])
            if child is None:
                leaf = _Node(key); leaf.is_end = True
                n.children[key[0]] = leaf; return
            k = _cpl(child.label, key)
            if k == len(child.label):
                key = key[k:]; n = child; continue
            split = _Node(child.label[:k])
            child.label = child.label[k:]
            split.children[child.label[0]] = child
            n.children[key[0]] = split
            if k == len(key):
                split.is_end = True
            else:
                rest = key[k:]
                leaf = _Node(rest); leaf.is_end = True
                split.children[rest[0]] = leaf
            return

    def search(self, key):
        n = self.root
        while key:
            child = n.children.get(key[0])
            if child is None:
                return False
            k = _cpl(child.label, key)
            if k < len(child.label):
                return False
            key = key[k:]; n = child
        return n.is_end

    def longest_prefix(self, key):
        n, best, spelled = self.root, None, ""
        while True:
            if n.is_end:
                best = spelled
            if not key:
                break
            child = n.children.get(key[0])
            if child is None:
                break
            k = _cpl(child.label, key)
            if k < len(child.label):
                break
            spelled += child.label; key = key[k:]; n = child
        return best


if __name__ == "__main__":
    t = Radix()
    for k in ["10", "1010", ""]:
        t.insert(k)
    print(repr(t.longest_prefix("10101")))  # '1010'
    print(repr(t.longest_prefix("1099")))   # '10'
    print(repr(t.longest_prefix("9")))      # ''
    print(t.search("10"))                   # True
    print(t.search("101"))                  # False

Complexity: every operation is O(L) where L is the key length; the tree has ≤ 2N−1 nodes. Longest-prefix match is the exact operation an IP router runs per packet.

Follow-ups the interviewer may ask¶

• Add delete with merge. Clear isEnd; if a node becomes single-child non-terminal, fuse its label into the child. (Covered in tasks.md.)
• Make it a binary PATRICIA over fixed-width keys. Switch the alphabet to bits and add skip-bit indices with a final full compare.
• Convert LPM to true IP routing. Encode CIDR prefixes as bitstrings of their significant bits and store next-hops at terminals.
• Make it concurrent. Discuss RCU or Optimistic Lock Coupling for read-mostly workloads.

Bonus Challenge: Count Nodes and Verify Compression¶

Extend the radix tree with nodeCount() and a check that the structure respects the ≤ 2N − 1 bound. This is a common follow-up to confirm you understand why the radix tree saves memory, not just that it does.

Python¶

def node_count(node):
    return 1 + sum(node_count(c) for c in node.children.values())


def key_count(node):
    return (1 if node.is_end else 0) + sum(key_count(c) for c in node.children.values())


def verify_bound(tree):
    n = key_count(tree.root)
    nodes = node_count(tree.root)
    # root is counted; for N >= 1 keys the bound is nodes <= 2N (root + 2N-1)
    assert nodes <= 2 * n + 1, f"compression violated: {nodes} nodes for {n} keys"
    return nodes, n


t = Radix()
for w in ["romane", "romanus", "romulus", "rubens", "ruber", "rubicon", "rubicundus"]:
    t.insert(w)
nodes, n = verify_bound(t)
print(f"{n} keys -> {nodes} nodes (bound 2N-1 = {2*n - 1})")
# 7 keys -> 13 nodes (bound 2N-1 = 13)  -- tight!

Go¶

func nodeCount(n *rnode) int {
    c := 1
    for _, ch := range n.children {
        c += nodeCount(ch)
    }
    return c
}

func keyCount(n *rnode) int {
    c := 0
    if n.isEnd {
        c = 1
    }
    for _, ch := range n.children {
        c += keyCount(ch)
    }
    return c
}

Why interviewers ask this: the answer reveals whether you understand that the radix tree's win is node count O(N), not faster per-operation time (search is O(L) for both plain and compressed tries). The tight 13 = 2×7 − 1 on this dataset is the proof in miniature — every internal node is a genuine branching point.

The deeper follow-up: "What would the plain trie's node count be?" Answer: roughly the number of distinct characters along all paths (~34 here), so the compression ratio is ~2.6× on this tiny set and grows with key length — the motivation for the whole structure.

Interview Strategy¶

When you see a problem involving strings or bitstrings plus any of:

• "most specific match" / "longest matching prefix" / "routing"
• "memory-efficient prefix lookup" / "dictionary that's too big as a plain trie"
• "in-memory index with range scans"
• "CIDR" / "IP forwarding" / "autocomplete with tight memory"

reach for a radix tree (or its binary PATRICIA form). If the interviewer says "trie" but the keys are long with little branching, propose the compressed variant and explain the O(N) node win.

Further Reading¶

• Morrison (1968) — the original PATRICIA paper.
• Leis, Kemper, Neumann (2013) — "The Adaptive Radix Tree", ICDE.
• Nilsson & Karlsson (1999) — "IP-Address Lookup Using LC-Tries", IEEE JSAC.
• The plain-trie interview set this builds on: 09-trees/05-trie/interview.md (esp. LC 208, 211, 648 — many are cleaner with a radix tree).
• Continue with tasks.md for hands-on implementation exercises.