Trees5 min read

N-ary Trees

When nodes can have any number of children — file systems, DOM, org charts

traverse: \(O(n)\)space: \(O(n)\)

An N-ary tree is a tree where each node can have any number of children — not just two. While binary trees restrict each parent to at most 2 children, N-ary trees lift that restriction entirely.

Real-world examples are everywhere:

File system — a folder can contain any number of files and subfolders
HTML DOM — a <div> can have dozens of child elements. A Trie is another specialized N-ary tree used for string prefix search
Organization chart — a manager can have any number of direct reports
Comment threads — a comment can have any number of replies
JSON/XML documents — nodes with variable numbers of children

Structure

An N-ary node typically looks like:

pseudocode

class Node:
  def __init__(self, val):
    self.val = val
    self.children = []  # List of Node references

The children list grows dynamically — a node with 3 children stores 3 references, a leaf stores an empty list.

◈ Explore N-ary tree

← → arrow keys to step · click elements to interact

N-ary Tree: Build & Traverse

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def preorder(node):
    if not node: return []
    result = [node.val]
    for child in node.children:
        result += preorder(child)
    return result

def postorder(node):
    if not node: return []
    result = []
    for child in node.children:
        result += postorder(child)
    result.append(node.val)
    return result

# Build tree:
#       1
#     / | \
#    3  2  4
#   / \
#  5   6
root = Node(1)
n3 = Node(3); n3.children = [Node(5), Node(6)]
root.children = [n3, Node(2), Node(4)]

print(preorder(root))   # [1, 3, 5, 6, 2, 4]
print(postorder(root))  # [5, 6, 3, 2, 4, 1]

Output

[1, 3, 5, 6, 2, 4]
[5, 6, 3, 2, 4, 1]

Traversing an N-ary tree

The same traversal strategies apply as with binary trees, just adapted for variable numbers of children:

Pre-order (DFS)

Visit the current node, then recursively visit each child in order:

pseudocode

def preorder(node):
  if node is None: return
  visit(node)
  for child in node.children:
    preorder(child)

Post-order (DFS)

Visit all children first, then the current node:

pseudocode

def postorder(node):
  if node is None: return
  for child in node.children:
    postorder(child)
  visit(node)

Level-order (BFS)

Visit nodes level by level using a queue — same as binary tree BFS, just enqueue all children instead of just two:

pseudocode

def levelorder(root):
  queue = [root]
  while queue:
    node = queue.pop(0)
    visit(node)
    queue.extend(node.children)

Serialization and deserialization

Storing an N-ary tree to disk or sending it over a network requires serialization. One common approach: encode each node's value followed by a count of its children, then recursively serialize each child. Another approach: use a special null marker to separate siblings from the parent's end of children list.

The popular LeetCode encoding for N-ary trees uses a level-order format with null separators between levels.

Note: Any N-ary tree can be converted to a binary tree using the "left-child right-sibling" representation: a node's left child pointer points to its first child, and its right child pointer points to its next sibling. This is how many file system implementations work internally.

N-ary tree vs. binary tree

When should you use each?

Use a binary tree when your domain has a natural "two-way split" (less/greater, true/false) or you need BST search properties
Use an N-ary tree when nodes naturally have a variable number of children (file systems, parse trees, org charts)

Height and depth

The height of an N-ary tree is the length of the longest root-to-leaf path. In a balanced N-ary tree with branching factor k, the height is \(O(log_k n)\) — which can be much smaller than a binary tree's \(\log_2(n)\). For example, a file system with average branching factor 20 can store millions of files in just 4-5 levels.

Complexity

Traversal (any order)Every node is visited exactly once

Linear\(O(n)\)

Find node by valueNo ordering property — must check all nodes

Linear\(O(n)\)

Insert childAppend to parent's children list

Instant\(O(1)\)

SpaceOne node per value + child list overhead

Linear\(O(n)\)

N-ary Tree: Level-Order & Max Depth

from collections import deque

class Node:
    def __init__(self, val): self.val=val; self.children=[]

def level_order(root):
    if not root: return []
    result = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            q.extend(node.children)
        result.append(level)
    return result

def max_depth(node):
    if not node: return 0
    if not node.children: return 1
    return 1 + max(max_depth(c) for c in node.children)

root=Node(1); n3=Node(3); n3.children=[Node(5),Node(6)]
root.children=[n3, Node(2), Node(4)]
print(level_order(root))  # [[1], [3, 2, 4], [5, 6]]
print(max_depth(root))    # 3

Output

[[1], [3, 2, 4], [5, 6]]
3

Challenge

Quick check

A file system folder tree has 1000 files and folders across 4 levels. What traversal would you use to calculate each folder's total size?

Binary Trees

A family tree where every parent has at most two children

→

Breadth-First Search

Explore a city map ring by ring — nearest neighbors first

→