BSTs and tries

Two structures with distinct interview roles: BSTs test whether you understand an invariant, tries test whether you recognise a prefix problem.

Binary search trees

The invariant: every node’s entire left subtree is smaller, entire right subtree is larger. Not just the immediate children — that’s the trap.

def is_valid_bst(root) -> bool:
    def check(node, lo=float("-inf"), hi=float("inf")) -> bool:
        if not node:
            return True
        if not (lo < node.val < hi):
            return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)

    return check(root)

The wrong answer — comparing each node only to its children — passes a tree like:

      10
     /  \
    5    15
        /  \
       6    20        <- 6 < 10, so this is NOT a valid BST

6 is smaller than the root but sits in the right subtree. Bounds must propagate down, which is what makes the recursive lo/hi version correct.

In-order traversal is sorted

The property most BST problems reduce to.

def inorder(node, out: list):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)

Applications: validate a BST (check the output is strictly increasing), kth smallest (stop at k), find two swapped nodes, convert to a sorted list.

For kth smallest, don’t materialise the whole list — use an iterative traversal and stop early:

def kth_smallest(root, k: int) -> int:
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

O(h + k) rather than O(n). Mentioning that improvement unprompted is a good signal.

Deletion — the three cases

The operation people fumble:

def delete(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        if not root.left:  return root.right
        if not root.right: return root.left
        succ = root.right
        while succ.left:
            succ = succ.left                 # leftmost of the right subtree
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

Balance is the caveat

A BST gives O(log n) operations only when balanced. Insert sorted data into a plain BST and you get a linked list — O(n) per operation.

Real implementations self-balance: red-black trees (Java’s TreeMap, C++ std::map), AVL trees, B-trees (database indexes). You won’t be asked to implement one; you should know why they exist.

In Python there is no built-in balanced BST. The practical answers:

Saying “in Python I’d reach for bisect or sortedcontainers rather than hand-rolling a BST” is the pragmatic answer.

Tries

A prefix tree. Each node holds one character; a path from the root spells a prefix.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, s: str) -> TrieNode | None:
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

is_word is essential and easy to forget: without it you can’t distinguish a stored word from a mere prefix of one.

When a trie beats a hash set

A hash set answers “is this exact string present” in O(1) — better than a trie’s O(len). The trie wins when you need prefixes:

• Autocomplete — all words with a given prefix.
• Longest matching prefix — IP routing, dictionary matching.
• Wildcard search — a . matching any character needs branching, which a hash set can’t do.
• Word search in a grid — the trie prunes the DFS the moment a path stops being a valid prefix.

That last one is the strongest example: without a trie you check every candidate word separately; with one, an entire branch of the search dies as soon as the prefix is unknown.

def find_words(board, words) -> list[str]:
    trie = Trie()
    for w in words:
        trie.insert(w)
    # DFS the grid, walking the trie in parallel; abandon a path the
    # instant the current prefix isn't in the trie.

Cost

Memory is the trade: one node per character per unique prefix, with a dict of children each. For a large dictionary that’s substantial. Mitigations: __slots__, arrays instead of dicts for a fixed alphabet, or a compressed trie (radix tree) that collapses single-child chains.

Interview angle

• “How do you validate a BST?” — propagate lo/hi bounds down the recursion. Comparing each node only to its immediate children is the classic wrong answer: it accepts a node that violates an ancestor’s constraint.
• “What’s special about in-order traversal of a BST?” — it yields sorted order. Most BST problems reduce to that: validation, kth smallest, finding swapped nodes.
• “Find the kth smallest element.” — iterative in-order, stopping at k. O(h + k) rather than building the full sorted list.
• “How do you delete a node with two children?” — replace its value with the in-order successor (leftmost node of the right subtree), then delete that successor, which by construction has at most one child.
• “Are BST operations O(log n)?” — only when balanced. Inserting sorted data into a plain BST degenerates to a linked list at O(n). Real implementations self-balance; in Python you’d use bisect or sortedcontainers rather than writing one.
• “When would you use a trie over a hash set?” — when you need prefix operations: autocomplete, longest-prefix matching, wildcard search, or pruning a search. For exact lookup a hash set is faster and smaller.