How does tree recursion change when a node holds a list of children instead of left and right?
answer
- count how many recursive calls one node makes
- arity in the type versus arity in the data
- what replaces the null-child guard
- one for-loop over the children list
- child links across the whole tree total n-1
basics
~10 sThe two hardcoded recursive calls become one loop over the children list, and the null-child check becomes an empty-children-list check. Every node is still visited exactly once, so a full traversal is still O(n).
solid answer
~50 sIn a binary shape the arity is baked into the node type, so the code says `recurse(left)` then `recurse(right)` and guards each call with a null test. With a children list the arity is data, not code: one `for` loop over the node's children, recursing on each. The base case moves too — "the child pointer is null" becomes "this node's children list is empty", which usually needs no explicit test, because a loop over an empty list runs zero times. Cost is unchanged: one call per node and `n - 1` child links followed in total, so a full walk stays O(n) however wide any node is. The traversal that does not survive the generalization is inorder — with `k` children there is no canonical place to put the node among them, so n-ary trees offer preorder, postorder and level-order only.
code
pseudocode · 9 linesPREORDER(node):
VISIT(node)
for child in CHILDREN(node):
PREORDER(child)
// binary version, for contrast:
// VISIT(node)
// if left(node) != null: PREORDER(left(node))
// if right(node) != null: PREORDER(right(node))go deeper
Be ready to write the loop version of a walk on the spot and to say the base case out loud: an empty children list, not a null child. Also recall that visiting every node is O(n) whatever the fanout.
Explain why the cost is unchanged by counting child links rather than nodes, and name inorder as the one binary traversal with no canonical n-ary meaning. Mention the reverse-push detail when converting the walk to an explicit stack.
Show that you pick the node representation from the model's real fanout rather than defaulting to two slots, and that you keep the children order stable through every walk, since in real hierarchies that order is displayed to users.
Own the consequence for an API: exposing children as an ordered sequence rather than named slots is what lets the model absorb new shapes without a type change, and it decides how every traversal in the codebase will be written.
## The node shape is the whole difference A binary node reserves two named slots, `left` and `right`. The arity — how many children a node may have — lives in the type itself, so the traversal code can name each child individually. An n-ary node instead holds a single collection of child references, usually in order, with no fixed upper bound. The arity has moved from the type into the data, and every piece of code that walks the tree has to follow. This is not an academic distinction. Directory trees, org charts and document element trees all have unbounded fanout: a folder can hold nine hundred entries, a manager can have five direct reports, a section element can wrap any number of children. A node type with two named slots cannot even represent those shapes, so the children list is the default representation for real hierarchical models — the binary shape is the special case, not the other way round. ## What changes in the code Three things, and only three: 1. **Two calls become a loop.** `recurse(left); recurse(right)` becomes `for child in children(node): recurse(child)`. The loop body is identical for every child; nothing about the algorithm depends on which position a child occupies. 2. **The null guard becomes an emptiness condition.** In the binary shape you must test each child pointer before recursing, because "no left child" is represented by a null slot. In the children-list shape there are no placeholder slots — a leaf simply has an empty list, so the loop runs zero times and the recursion terminates on its own. You often need no explicit base-case branch beyond guarding the initial call on an empty tree. 3. **Per-child work becomes accumulation.** Anything you did with two named results (`max(leftHeight, rightHeight)`, `leftSum + rightSum`) becomes a fold over the loop: a running maximum, a running sum, a count. A generalized preorder walk is therefore: visit the node, then loop over its children and recurse. Postorder is the same body with the visit moved after the loop. ## What does not change: the cost The common wrong answer is that unbounded fanout makes traversal more expensive — something like O(n · b) where `b` is the maximum branching factor. It does not. Count the work by edges rather than by nodes: the loop body executes once per child link in the whole tree, and a rooted tree with `n` nodes has exactly `n - 1` child links. Add one visit per node and the total is O(n). A very wide tree and a very deep tree with the same node count cost the same to walk. What the shape does change is *where* the cost of the walk lives. A deep, narrow tree pushes many nested recursive calls; a shallow, very wide tree pushes few but holds a large frontier if you traverse level by level with a queue. The node count bounds the total either way. ## What has no n-ary generalization Inorder. In a binary tree, inorder means "left subtree, node, right subtree" — the node sits in the unique gap between its two children. With `k` children there are `k + 1` gaps and no principled reason to choose one, so inorder has no canonical n-ary meaning. Preorder (node before its children), postorder (node after all its children) and level-order (tier by tier) all generalize cleanly, because each is defined relative to *the whole set* of children rather than to a specific child position. Candidates who answer "you'd do inorder by visiting the node after the first child" have invented a convention, not recalled one; the honest answer is that the ordering does not survive the generalization. ## Ordering and stability of children One subtlety worth stating out loud: the children list is *ordered*, and that order is usually meaningful — the order of entries in a listing, the order of elements in a document, the display order of reports under a manager. A traversal must preserve it, which means iterating the list front to back. If you rewrite a recursive walk as an iterative one with an explicit stack, pushing children in list order makes them pop in reverse, so you push them in reverse order to keep the original left-to-right visit sequence. That reversal is one of the most common bugs when people port binary traversal habits to n-ary shapes. ## How to answer it in an interview Say the arity moves from the type into the data; show the loop; name the base case as "empty children list" rather than "null child"; assert O(n) with the `n - 1` edges argument; and volunteer that inorder does not generalize. That is the complete answer at this level.
- If a leaf just has an empty children list, do you need a null check anywhere at all?Usually only once, at the entry point, for an empty tree with no root. Inside the walk you never dereference a missing child, because you only iterate over child references that actually exist. That is the practical benefit of the list shape: the absent-child case stops being a special value you must test and becomes a list of length zero.
- Does unbounded fanout make a full traversal asymptotically slower?No. The loop body runs once per child link, and a rooted tree with n nodes has exactly n-1 child links, so the total work is O(n) regardless of how wide any single node is. Branching factor affects the tree's height and the peak width of a level-order frontier, not the total number of nodes you touch.
- If you rewrite the walk iteratively with an explicit stack, what breaks first?Child order. Pushing a node's children front to back makes them pop back to front, so the visit sequence silently reverses at every node. You push the children in reverse list order to recover the original left-to-right preorder — and if the children's order is meaningful, as in a document or a listing, that reversal is a real bug, not a cosmetic one.
A binary node is a form with two named boxes to fill; an n-ary node is a form with a list you keep adding rows to.
saying these in an interview costs you the question
- Claims traversal becomes O(n times branching factor)
- Keeps per-child null checks instead of iterating the list
- Says inorder generalizes naturally to n-ary trees
- Assumes each node must declare a fixed maximum child count
- Ignores that the children list is ordered and the order matters