N-ary Tree Preorder Traversal
Easy · Trees · Tree · Depth-First Search · Stack
Problem
Given the root of an n-ary tree (each node has a value and a list of any number of children), return the preorder traversal of its values: visit a node, then each child's subtree from left to right.
Trees are written in level order, with each node's group of children followed by null (None in Python). For example [1,null,3,2,4,null,5,6] is the root 1 with children 3, 2, 4, where 3 has children 5 and 6.
The recursive version is short; also write one that uses an explicit stack.
Examples
Input: root = [1,null,2,3,4,null,5,6,null,7] Output: [1,2,5,6,3,7,4]
Node 1 has children 2, 3, 4; node 2 has 5 and 6; node 3 has 7. Each node comes before its subtree.
Input: root = [8] Output: [8]
Only the root.
Input: root = [] Output: []
No nodes, no values.
Constraints
- The tree has between 0 and 10^4 nodes.
- 0 <= Node.val <= 10^4
- The height of the tree is at most 1000.
Approaches
- Recursion that concatenates child lists — time O(n · h), space O(n · h)
Follow-up
The stack version never recurses, so deep trees cannot overflow the call stack. Postorder comes from the same loop: push children in their normal order, record nodes, and reverse the result at the end.
Related problems
Start free on Cariara · Coding problems · System design studio
