TreesData structureaka general tree, k-ary tree, rose tree

N-ary Tree

A rooted tree in which each node can have any number of children, stored as a child list, and traversed with the same DFS/BFS ideas as binary trees.

▶ VisualizePattern: Breadth-First SearchPractice (3)
Progress

Definition

An N-ary tree drops the two-children limit of a Binary Tree: each node has an ordered list of zero or more children. File systems, DOM trees, organization charts, JSON documents and the recursion trees of Recursion & Backtracking searches are all N-ary trees.

Storage is either a children array per node, a parent array (parent[i]) for immutable trees, or a general Adjacency List when the tree is given as n - 1 edges. A classic trick, the left-child right-sibling encoding, represents any N-ary tree as a binary tree: left points to the first child, right to the next sibling.

hierarchicalchildren listDFSBFSfile system

Intuition

A mental model before the formal terms.

Think of a folder tree in a file explorer. A folder can hold any number of files or sub-folders. Computing the size of a folder means summing the sizes of everything inside — a postorder traversal. Listing every file at "depth 2" is a level-order traversal.

Every binary tree algorithm that recurses on left and right becomes a loop over children; that is the only change.

How it works

  1. Node: value plus children: Node[]. The root has no parent.
  2. DFS preorder: visit the node, then recurse into each child in order. Postorder: recurse first, then visit — used for subtree sizes, heights, and "delete this subtree".
  3. BFS: queue the root; repeatedly pop, visit, push all children. Track level size for level-order output.
  4. When the tree arrives as edges, build an adjacency list, pick a root, and DFS while passing the parent to avoid walking back up the edge.
  5. Serialization: preorder with child counts (or a sentinel after each node's children) reconstructs the tree uniquely.

Why it works

The recursive definition (a node plus a list of subtrees) supports structural induction just like binary trees; correctness of a subtree computation lifts to the whole tree.

Every node is enqueued or recursed exactly once and every edge is examined once, so traversals are O(n) regardless of branching factor.

Operations

OperationDescriptionCost
addChild(parent, value)Append a new node to the parent's child list.O(1)
traverse (DFS / BFS)Visit all nodes; loop over children instead of left/right.O(n)
height / sizePostorder aggregation over children.O(n)
searchNo ordering, so every node may need to be checked.O(n)
removeChildRemove a subtree from its parent's list.O(k)

Recognition

How to tell a problem wants this.

  • The input has a parent/child relationship with variable fan-out: "manager of", "directory contains", "category has subcategories".
  • Given n nodes and n - 1 edges and told it is a tree (connected, acyclic).
  • Problems on tree DP (Tree DP), subtree queries, or lowest common ancestor in a general tree.
“minimum steps” → Breadth-First Search“connected groups” → Depth-First Search“binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

EFBGCHIJDA
DFS order
empty
Call stack
empty
1/32DFS (preorder) from A: visit a node, then recurse into each child left to right — the whole first subtree is finished before the second starts.
Being visitedOn stack / in queueDone
PseudocodeLearn N-ary Tree →
1dfs(node): visit(node)
2  for child in node.children: dfs(child)
3bfs(root): queue = [root]
4  while queue: node = queue.popleft(); visit(node)
5    for child in node.children: queue.append(child)
Variables
modedfs
nodes10
Complexity
access O(n)
search O(n)
insert O(1)
delete O(k)
Speed

Pseudocode

1dfs(node):
2  visit(node)
3  for child in node.children: dfs(child)
4height(node):
5  return 1 + max(height(c) for c in children, default 0)

Implementation

1from collections import deque
2from typing import Generic, Optional, TypeVar
3 
4T = TypeVar("T")
5 
6 
71 · Node with a list of children
8class NaryNode(Generic[T]):
9    def __init__(self, val: T) -> None:
10        self.val = val
11        self.children: list["NaryNode[T]"] = []
12 
13 
14class NaryTree(Generic[T]):
15    def __init__(self) -> None:
16        self.root: Optional[NaryNode[T]] = None
17 
182 · Add a child under a given parent
19    def add_child(self, parent: Optional[NaryNode[T]], val: T) -> NaryNode[T]:
20        node = NaryNode(val)
21        if parent is None:
22            self.root = node
23        else:
24            parent.children.append(node)
25        return node
26 
273 · Preorder and postorder DFS
28    def preorder(self) -> list[T]:
29        out: list[T] = []
30 
31        def go(n: Optional[NaryNode[T]]) -> None:
32            if n is None:
33                return
34            out.append(n.val)
35            for c in n.children:
36                go(c)
37 
38        go(self.root)
39        return out
40 
41    def postorder(self) -> list[T]:
42        out: list[T] = []
43 
44        def go(n: Optional[NaryNode[T]]) -> None:
45            if n is None:
46                return
47            for c in n.children:
48                go(c)
49            out.append(n.val)
50 
51        go(self.root)
52        return out
53 
544 · BFS level order
55    def level_order(self) -> list[list[T]]:
56        if self.root is None:
57            return []
58        levels: list[list[T]] = []
59        q = deque([self.root])
60        while q:
61            level: list[T] = []
62            for _ in range(len(q)):
63                n = q.popleft()
64                level.append(n.val)
65                q.extend(n.children)
66            levels.append(level)
67        return levels
68 
695 · Height via postorder combine over all children
70    def height(self) -> int:
71        def go(n: Optional[NaryNode[T]]) -> int:
72            if n is None:
73                return 0
74            return 1 + max((go(c) for c in n.children), default=0)
75 
76        return go(self.root)
Walkthrough
  1. NaryNode(Generic[T]) uses TypeVar so type hints carry the value type.
  2. add_child(None, val) creates the root; otherwise the node is appended to the parent's children list.
  3. Preorder and postorder are nested closures that loop over n.children.
  4. level_order uses deque and q.extend(n.children) to enqueue all children in one call.
  5. height uses max(..., default=0) so leaves (empty generator) do not raise ValueError.
Complexity (this implementation)
time O(n) per traversal · space O(h) recursion / O(w) queue

Python's 1000-frame recursion limit is hit by a 1000-deep path; use an explicit stack for deep trees.

Language notes
  • max(iterable, default=0) is the idiomatic guard for possibly empty sequences.
  • deque.extend is O(k) for k children and avoids a Python-level loop.
  • Nested dicts/lists are often used directly as n-ary trees in Python (e.g. parsed JSON).
Common mistakes in this language
  • Calling max() on an empty generator without default, which raises ValueError.
  • Using a mutable default children=[] in __init__ and sharing it across all nodes.
  • Recursing on deep trees; convert to an explicit stack when depth can exceed a few hundred.
Language differences that matter here
  • Empty-children max: Python needs default=0, JS/TS need an explicit 0 argument to Math.max, C++ uses a running maximum.
  • JS/TS spread into push/Math.max has an argument limit around 100k; C++ and Python have no equivalent limit.
  • TS and Python versions are generic over the value type; C++ would use a template; JS is dynamically typed anyway.

Complexity

OperationAverageWorstNote
AccessO(n)O(n)
SearchO(n)O(n)
InsertO(1)O(1)Given the parent node.
DeleteO(k)O(k)k = parent's child count (list removal).
UpdateO(1)O(1)Given the node.
TraversalO(n)O(n)
HeightO(n)O(n)
SpaceO(n)Child lists total n - 1 references. DFS stack O(h), BFS queue O(max level width).

Advantages & disadvantages

Advantages
  • Models real hierarchies directly without artificial binarization.
  • All the binary tree algorithms transfer with a loop over children.
  • Cheap O(1) child insertion at the end of the list.
Disadvantages
  • No ordering invariant, so search is O(n).
  • Variable-size child lists mean more allocations and worse locality than fixed-arity trees.
  • Wide, shallow trees make recursion cheap but BFS queues large; deep narrow trees do the opposite.

Use cases

  • File systems, DOM and XML/JSON document trees.
  • Organizational charts, taxonomies and category hierarchies.
  • Game trees and recursion trees in Recursion & Backtracking and Divide and Conquer.
  • The Trie is an N-ary tree with alphabet-sized fan-out.
Use it when
  • Hierarchies with variable fan-out (files, DOM, org charts, taxonomies).
  • Tree DP and subtree aggregation on a tree given as edges.
  • Prefix structures — a Trie is the N-ary tree specialized to strings.
Avoid it when

Alternatives

Binary TreeAdjacency ListTrieB-Tree

Common mistakes

  • Walking back to the parent when the tree is given as undirected edges — pass the parent and skip it.
  • Using max([]) without a default on leaf nodes, which throws in Python.
  • Deep recursion on a path-shaped tree of 10^5 nodes; use an explicit stack.
  • Serializing without child counts or sentinels, making the structure ambiguous.

Interview patterns

  • Level-order / max depth / preorder on an N-ary tree (direct binary-tree translations).
  • Tree DP: subtree sums, longest path, rerooting.
  • Encode an N-ary tree as a binary tree with left-child right-sibling.
  • Clone or serialize a general tree.
Interview questions on this
Mock interviews

Interview problems

Binary Tree Level Order TraversalmediumLowest Common Ancestor of a Binary TreemediumSerialize and Deserialize Binary Treehard