# LeetCode 589: N-ary Tree Preorder Traversal

## Problem Restatement

We are given the `root` of an N-ary tree.

An N-ary tree is a tree where each node can have any number of children.

We need to return the preorder traversal of the tree's node values. In preorder traversal, we visit:

1. The current node.
2. Its children from left to right.

The number of nodes is in the range `[0, 10^4]`, node values are between `0` and `10^4`, and the tree height is at most `1000`. The follow-up asks for an iterative solution.

## Input and Output

| Item | Meaning |
|---|---|
| `root` | Root node of an N-ary tree |
| Output | List of node values in preorder |
| Empty tree | Return `[]` |

The node structure is usually given as:

```python
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
```

Example function shape:

```python
def preorder(root: "Node") -> list[int]:
    ...
```

## Examples

Example 1:

```text
root = [1,null,3,2,4,null,5,6]
```

This represents:

```text
        1
      / | \
     3  2  4
    / \
   5   6
```

Output:

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

We visit `1` first, then the subtree rooted at `3`, then `2`, then `4`.

Example 2:

```python
root = []
```

Output:

```python
[]
```

An empty tree has no nodes to visit.

## First Thought: Recursive DFS

Preorder traversal is naturally recursive.

For each node:

1. Add the node's value to the answer.
2. Recursively visit each child from left to right.

This matches the definition of preorder exactly.

## Key Insight

A tree traversal is a depth-first search.

For preorder, the node is processed before its children.

So the recursive rule is:

```text
visit node
then visit each child in order
```

For an N-ary tree, the only difference from a binary tree is that instead of `left` and `right`, each node has a list of children.

## Algorithm

1. Create an empty result list.
2. Define a DFS function.
3. If the current node is `None`, stop.
4. Append the current node's value.
5. For each child in `node.children`, recursively call DFS.
6. Return the result list.

## Correctness

The algorithm appends a node's value before visiting any of its children. This matches the first rule of preorder traversal.

Then it visits the children in the same left-to-right order as they appear in `node.children`. For each child, the same rule is applied recursively, so the entire child subtree is traversed in preorder before moving to the next child.

The base case handles an empty node by adding nothing, which is correct for an empty subtree.

Therefore, the result contains exactly the preorder traversal of the N-ary tree.

## Complexity

Let:

```text
n = number of nodes in the tree
h = height of the tree
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | The recursion stack can contain one path from root to leaf |

The output list also uses `O(n)` space.

## Implementation

```python
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: "Node") -> list[int]:
        result = []

        def dfs(node: "Node") -> None:
            if node is None:
                return

            result.append(node.val)

            for child in node.children:
                dfs(child)

        dfs(root)

        return result
```

## Code Explanation

The result list stores the traversal:

```python
result = []
```

The helper function visits one subtree:

```python
def dfs(node):
```

The empty tree case is:

```python
if node is None:
    return
```

For preorder, we append the current value before visiting children:

```python
result.append(node.val)
```

Then we recursively traverse each child:

```python
for child in node.children:
    dfs(child)
```

Finally, the traversal starts at the root:

```python
dfs(root)
```

## Iterative Implementation

The follow-up asks for an iterative solution.

Use a stack.

The main detail is child order. Since a stack is last-in, first-out, we push children in reverse order. That makes the leftmost child processed first.

```python
class Solution:
    def preorder(self, root: "Node") -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            for child in reversed(node.children):
                stack.append(child)

        return result
```

For example, if node `1` has children:

```python
[3, 2, 4]
```

we push them as:

```python
4, 2, 3
```

Then `3` is popped first, preserving preorder.

## Testing

```python
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []

def run_tests():
    s = Solution()

    root = Node(1, [
        Node(3, [Node(5), Node(6)]),
        Node(2),
        Node(4),
    ])
    assert s.preorder(root) == [1, 3, 5, 6, 2, 4]

    assert s.preorder(None) == []

    single = Node(1)
    assert s.preorder(single) == [1]

    chain = Node(1, [Node(2, [Node(3)])])
    assert s.preorder(chain) == [1, 2, 3]

    wide = Node(1, [Node(2), Node(3), Node(4)])
    assert s.preorder(wide) == [1, 2, 3, 4]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Sample tree | Checks standard preorder behavior |
| Empty tree | Returns an empty list |
| Single node | Returns only the root |
| Deep chain | Checks recursion down one path |
| Wide tree | Checks children are visited left to right |