N-ary Trees and Trie Applications

Binary trees restrict each node to at most 2 children. N-ary trees lift that restriction — each node can have any number of children. The most important N-ary tree in practice is the Trie (prefix tree), used in autocomplete systems, spell checkers, and IP routing tables.

N-ary tree representation

Each node stores a value and a list of children:

class NaryNode:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children else []

Example tree:

        1
      / | \
     2  3  4
    / \    |
   5   6   7

# Building the tree:
node5 = NaryNode(5)
node6 = NaryNode(6)
node7 = NaryNode(7)
node2 = NaryNode(2, [node5, node6])
node3 = NaryNode(3)
node4 = NaryNode(4, [node7])
root = NaryNode(1, [node2, node3, node4])

N-ary tree traversals

BFS (level order)

from collections import deque

def bfs_nary(root):
    """Level order traversal of N-ary tree."""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            for child in node.children:
                queue.append(child)
        result.append(level)

    return result

# Example: [[1], [2, 3, 4], [5, 6, 7]]

DFS (preorder)

def preorder_nary(root):
    """Preorder traversal: root, then children left to right."""
    if not root:
        return []

    result = [root.val]
    for child in root.children:
        result.extend(preorder_nary(child))
    return result

# Example: [1, 2, 5, 6, 3, 4, 7]

DFS (postorder)

def postorder_nary(root):
    """Postorder traversal: children left to right, then root."""
    if not root:
        return []

    result = []
    for child in root.children:
        result.extend(postorder_nary(child))
    result.append(root.val)
    return result

# Example: [5, 6, 2, 3, 7, 4, 1]

Iterative preorder

def preorder_iterative(root):
    """Iterative preorder using a stack."""
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push children in reverse order (rightmost first)
        # so leftmost is processed first
        for child in reversed(node.children):
            stack.append(child)

    return result

N-ary tree problems

Maximum depth

def max_depth_nary(root):
    """Maximum depth of N-ary tree."""
    if not root:
        return 0
    if not root.children:
        return 1
    return 1 + max(max_depth_nary(child) for child in root.children)

Count nodes

def count_nodes_nary(root):
    """Total number of nodes in N-ary tree."""
    if not root:
        return 0
    return 1 + sum(count_nodes_nary(child) for child in root.children)

Diameter of N-ary tree

def diameter_nary(root):
    """Diameter of N-ary tree (longest path between any two nodes)."""
    max_diameter = [0]

    def depth(node):
        if not node:
            return 0

        # Get the two largest depths among children
        top_two = [0, 0]
        for child in node.children:
            d = depth(child)
            if d > top_two[0]:
                top_two[1] = top_two[0]
                top_two[0] = d
            elif d > top_two[1]:
                top_two[1] = d

        max_diameter[0] = max(max_diameter[0], top_two[0] + top_two[1])
        return 1 + top_two[0]

    depth(root)
    return max_diameter[0]

Encode N-ary tree to binary tree

A common trick: represent an N-ary tree as a binary tree using left-child, right-sibling encoding:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def encode(root):
    """Convert N-ary tree to binary tree."""
    if not root:
        return None

    binary_root = TreeNode(root.val)

    if root.children:
        binary_root.left = encode(root.children[0])

    # Siblings become right children
    current = binary_root.left
    for i in range(1, len(root.children)):
        current.right = encode(root.children[i])
        current = current.right

    return binary_root

def decode(root):
    """Convert binary tree back to N-ary tree."""
    if not root:
        return None

    nary_root = NaryNode(root.val)

    # Left child and its right chain are the children
    current = root.left
    while current:
        nary_root.children.append(decode(current))
        current = current.right

    return nary_root

Trie (prefix tree)

A Trie is a specialized N-ary tree for storing strings. Each edge represents a character, and paths from root to marked nodes represent words.

Basic Trie implementation

class TrieNode:
    def __init__(self):
        self.children = {}  # char → TrieNode
        self.is_end = False  # marks end of a word

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

    def insert(self, word):
        """Insert a word into the trie. O(m) where m = len(word)."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """Check if word exists in trie. O(m)."""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        """Check if any word starts with prefix. O(m)."""
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        """Navigate to the node at end of prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Using the Trie

trie = Trie()

# Insert words
for word in ["cat", "car", "card", "care", "do", "dog", "done"]:
    trie.insert(word)

# Search
print(trie.search("car"))      # True
print(trie.search("ca"))       # False (prefix, not a word)
print(trie.search("card"))     # True

# Prefix check
print(trie.starts_with("ca"))  # True
print(trie.starts_with("dog")) # True
print(trie.starts_with("dox")) # False

Trie time and space complexity

Operation	Time	Space
Insert	O(m)	O(m) new nodes
Search	O(m)	O(1)
Starts with	O(m)	O(1)
Delete	O(m)	O(1)

Where m is the length of the word. Total space is O(n * m) in the worst case for n words of average length m, but sharing common prefixes saves space.

Autocomplete with Trie

Find all words that start with a given prefix:

def autocomplete(self, prefix):
    """Return all words starting with prefix."""
    node = self._find_node(prefix)
    if not node:
        return []

    results = []
    self._collect_words(node, prefix, results)
    return results

def _collect_words(self, node, prefix, results):
    """DFS to collect all words from this node."""
    if node.is_end:
        results.append(prefix)

    for char, child_node in sorted(node.children.items()):
        self._collect_words(child_node, prefix + char, results)

Top-k autocomplete

For a production autocomplete, you want the top k most frequent completions:

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

    def insert(self, word, frequency=1):
        """Insert word with frequency count."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        if not hasattr(node, 'freq'):
            node.freq = 0
        node.freq += frequency

    def top_k(self, prefix, k=5):
        """Return top k completions by frequency."""
        node = self._find_node(prefix)
        if not node:
            return []

        import heapq
        heap = []  # min-heap of (freq, word)
        self._collect_with_freq(node, prefix, heap, k)

        # Sort by frequency descending
        result = []
        while heap:
            freq, word = heapq.heappop(heap)
            result.append(word)
        return result[::-1]

    def _collect_with_freq(self, node, prefix, heap, k):
        import heapq
        if node.is_end:
            freq = getattr(node, 'freq', 1)
            if len(heap) < k:
                heapq.heappush(heap, (freq, prefix))
            elif freq > heap[0][0]:
                heapq.heapreplace(heap, (freq, prefix))

        for char, child in node.children.items():
            self._collect_with_freq(child, prefix + char, heap, k)

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Spell checker with Trie

Check if a word exists, suggest corrections:

def spell_check(trie, word):
    """Check spelling and suggest corrections within edit distance 1."""
    if trie.search(word):
        return True, []

    suggestions = set()
    alphabet = 'abcdefghijklmnopqrstuvwxyz'

    # Substitution: replace each character
    for i in range(len(word)):
        for c in alphabet:
            candidate = word[:i] + c + word[i+1:]
            if trie.search(candidate):
                suggestions.add(candidate)

    # Insertion: add a character at each position
    for i in range(len(word) + 1):
        for c in alphabet:
            candidate = word[:i] + c + word[i:]
            if trie.search(candidate):
                suggestions.add(candidate)

    # Deletion: remove each character
    for i in range(len(word)):
        candidate = word[:i] + word[i+1:]
        if trie.search(candidate):
            suggestions.add(candidate)

    return False, list(suggestions)

Wildcard search with Trie

Support . as a wildcard matching any single character (LeetCode 211):

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

    def add_word(self, word):
        """Add a word to the dictionary."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """Search with '.' as wildcard for any character."""
        return self._search(self.root, word, 0)

    def _search(self, node, word, index):
        if index == len(word):
            return node.is_end

        char = word[index]

        if char == '.':
            # Try all children
            for child in node.children.values():
                if self._search(child, word, index + 1):
                    return True
            return False
        else:
            if char not in node.children:
                return False
            return self._search(node.children[char], word, index + 1)

Usage

wd = WordDictionary()
wd.add_word("bad")
wd.add_word("dad")
wd.add_word("mad")

print(wd.search("pad"))   # False
print(wd.search("bad"))   # True
print(wd.search(".ad"))   # True (matches bad, dad, mad)
print(wd.search("b.."))   # True (matches bad)
print(wd.search("..."))   # True (matches any 3-letter word)

Word search in a grid (Trie + backtracking)

A classic problem: find all words from a dictionary in a grid of characters (LeetCode 212):

def find_words(board, words):
    """Find all words from dictionary in the grid."""
    # Build trie from words
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.word = word  # store the word at the end node

    rows, cols = len(board), len(board[0])
    result = set()

    def backtrack(r, c, node):
        char = board[r][c]
        if char not in node.children:
            return

        next_node = node.children[char]
        if next_node.is_end:
            result.add(next_node.word)

        # Mark as visited
        board[r][c] = '#'

        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                backtrack(nr, nc, next_node)

        # Restore
        board[r][c] = char

    for r in range(rows):
        for c in range(cols):
            backtrack(r, c, root)

    return list(result)

Counting words with prefix

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
                node.children[char].prefix_count = 0
            node = node.children[char]
            node.prefix_count += 1
        node.is_end = True

    def count_prefix(self, prefix):
        """Count how many words have this prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.prefix_count

Deleting from a Trie

def delete(self, word):
    """Delete a word from the trie."""
    self._delete(self.root, word, 0)

def _delete(self, node, word, depth):
    if depth == len(word):
        if not node.is_end:
            return False  # word not found
        node.is_end = False
        return len(node.children) == 0  # can delete if no children

    char = word[depth]
    if char not in node.children:
        return False

    should_delete = self._delete(node.children[char], word, depth + 1)

    if should_delete:
        del node.children[char]
        return not node.is_end and len(node.children) == 0

    return False

Trie vs hash set

Operation	Trie	Hash Set
Insert	O(m)	O(m) average
Search	O(m)	O(m) average
Prefix search	O(m + k)	O(n * m)
Autocomplete	O(m + k)	Not supported
Space	More (pointers)	Less (flat)
Ordered	Yes (alphabetical)	No

Use a Trie when you need prefix operations. Use a hash set when you only need exact lookup.

Practice problems

1. Implement Trie (LeetCode 208) — The foundation
2. Add and Search Word (LeetCode 211) — Wildcard search
3. Word Search II (LeetCode 212) — Trie + backtracking on grid
4. Replace Words (LeetCode 648) — Find shortest prefix in Trie
5. Maximum XOR of Two Numbers (LeetCode 421) — Bitwise Trie
6. N-ary Tree Level Order (LeetCode 429) — BFS on N-ary tree
7. N-ary Tree Preorder (LeetCode 589) — DFS traversal
8. Maximum Depth of N-ary Tree (LeetCode 559)
9. Encode N-ary to Binary Tree (LeetCode 431)

Key takeaways

• N-ary trees generalize binary trees — each node has a list of children
• All binary tree algorithms adapt to N-ary: replace left/right with for child in children
• Tries are specialized N-ary trees for strings, with one edge per character
• Tries excel at prefix operations: autocomplete, prefix count, starts-with queries
• Wildcard search in a Trie uses backtracking through all children for wildcard characters
• Real-world uses: search engines, DNS resolution, IP routing tables, spell checkers