N-ary Tree Preorder Traversal - Video Solutions

Problem Overview: Given the root of an N-ary tree, return its preorder traversal. In preorder traversal, you visit the current node first, then recursively process each child from left to right.

Approach 1: Recursive DFS (Time: O(n), Space: O(h))

The most natural way to solve this problem is recursion using Depth-First Search. Start at the root, add the node's value to the result list, then recursively traverse each child in order. Because preorder requires visiting the node before its children, the operation sequence is: visit node → iterate children → recurse. Each node is processed exactly once, giving O(n) time complexity where n is the number of nodes. The recursion stack grows with the height of the tree, so the auxiliary space is O(h). This approach is concise and mirrors the definition of preorder traversal directly.

Approach 2: Iterative Traversal with Stack (Time: O(n), Space: O(n))

An iterative solution replaces recursion with an explicit stack. Push the root node onto the stack, then repeatedly pop the top node, record its value, and push its children onto the stack. The key detail is the order: push children in reverse order so the leftmost child is processed first when popped. This preserves preorder traversal order. Every node enters and leaves the stack once, so the time complexity remains O(n). The stack may contain up to O(n) nodes in the worst case (for example, a wide level in the tree). This method avoids recursion and works well in environments where recursion depth could be limited.

Recommended for interviews: The recursive DFS approach is usually expected first because it directly expresses preorder traversal and is easy to implement correctly. Interviewers often accept it as the primary solution. The iterative stack version demonstrates deeper understanding of traversal mechanics and recursion simulation, which can strengthen your answer if follow-up questions ask for an iterative implementation.