LeetCode 589 - N-ary Tree Preorder Traversal

The problem asks for a preorder traversal of an n-ary tree. In a preorder traversal, the order of visiting nodes is: first the root node, then recursively all the children from left to right.

leetcodeeasystacktreedepth-first-search

LeetCode Problem 589

Difficulty: 🟢 Easy
Topics: Stack, Tree, Depth-First Search

Solution

Problem Understanding

The problem asks for a preorder traversal of an n-ary tree. In a preorder traversal, the order of visiting nodes is: first the root node, then recursively all the children from left to right. The input is given as the root node of an n-ary tree, where each node has a value and a list of children nodes. The output should be a flat list of integers representing the values of nodes visited in preorder.

The tree can have up to 10,000 nodes, and its height can be up to 1000. Each node's value is between 0 and 10,000. This means the solution must handle potentially large, deep trees efficiently. Edge cases include an empty tree (root = None), a tree with only a single node, or nodes with no children.

The problem explicitly mentions a follow-up for an iterative solution, meaning a stack-based approach is expected to avoid recursion stack overflow in deep trees.

Approaches

A brute-force approach is to use recursive preorder traversal. This involves defining a recursive helper function that first adds the current node’s value to the result list and then recursively traverses each child in order. This approach is simple and directly matches the definition of preorder traversal. It is correct for all inputs, but for very deep trees near the maximum height of 1000, Python’s recursion limit could be exceeded, and iterative traversal is safer.

The optimal approach is an iterative solution using a stack. By pushing nodes onto a stack and processing them in a last-in, first-out manner, we can mimic the recursive traversal. When adding children to the stack, they must be pushed in reverse order so that the leftmost child is processed first. This avoids recursion and is safer for deep trees.

Approach Time Complexity Space Complexity Notes
Recursive Brute Force O(N) O(H) Uses call stack, may overflow for deep trees (H = height)
Iterative Stack O(N) O(H) Safe for deep trees, explicitly uses stack to track nodes

Algorithm Walkthrough

  1. Check for empty tree: If the root is None, immediately return an empty list.
  2. Initialize stack and result: Create a stack initialized with the root node. Create an empty list result to store traversal output.
  3. Process stack until empty: While the stack is not empty, pop a node from the top of the stack.
  4. Add node value: Append the popped node’s value to result.
  5. Push children in reverse order: For each child of the popped node, push them onto the stack in reverse order. This ensures the leftmost child is processed first, preserving preorder.
  6. Repeat: Continue popping and processing nodes until the stack is empty.
  7. Return result: After the stack is empty, return the result list, which now contains the preorder traversal.

Why it works: The stack ensures that nodes are visited in preorder by processing the root first and pushing children in reverse order. The invariant is that at every iteration, the top of the stack is the next node to be visited in preorder, guaranteeing correct traversal.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

from typing import List, Optional

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.children:
                stack.extend(reversed(node.children))
        
        return result

The implementation starts by checking for an empty tree. The stack is initialized with the root node, and we process nodes iteratively. Each node value is appended to the result, and its children are pushed onto the stack in reverse order to maintain the correct preorder traversal. The algorithm stops when all nodes are visited.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    
    stack := []*Node{root}
    result := []int{}
    
    for len(stack) > 0 {
        n := len(stack) - 1
        node := stack[n]
        stack = stack[:n]
        result = append(result, node.Val)
        
        for i := len(node.Children) - 1; i >= 0; i-- {
            stack = append(stack, node.Children[i])
        }
    }
    
    return result
}

In Go, we handle nil for empty trees explicitly. Slices are used as a stack, and children are pushed in reverse order. Unlike Python, Go requires manual slice manipulation to pop the last element.

Worked Examples

Example 1: root = [1,null,3,2,4,null,5,6]

Initial stack: [1], result: []

Step Stack Result
1 [1] []
2 [] [1]
3 [4,2,3] [1]
4 [4,2] [1,3]
5 [4,2,6,5] [1,3]
6 [4,2,6] [1,3,5]
7 [4,2] [1,3,5,6]
8 [4] [1,3,5,6,2]
9 [] [1,3,5,6,2,4]

Output: [1,3,5,6,2,4]

Complexity Analysis

Measure Complexity Explanation
Time O(N) Each node is visited exactly once
Space O(H) Stack holds at most H nodes (tree height) at any time

The iterative solution ensures we never exceed O(H) additional space, avoiding recursion limits and handling deep trees efficiently.

Test Cases

# test cases
# Provided examples
assert Solution().preorder(None) == []  # empty tree
assert Solution().preorder(Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])) == [1,3,5,6,2,4]
assert Solution().preorder(Node(1, [Node(2), Node(3, [Node(6), Node(7, [Node(11, [Node(14)])])]), Node(4, [Node(8, [Node(12)])]), Node(5, [Node(9), Node(13)]), Node(10)])) == [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

# Edge cases
assert Solution().preorder(Node(1)) == [1]  # single node
assert Solution().preorder(Node(1, [])) == [1]  # node with empty children list
assert Solution().preorder(Node(1, [Node(2), Node(3), Node(4)])) == [1,2,3,4]  # multiple children, no grandchildren
Test Why
None Tests empty tree
Single node Validates correct handling of leaf nodes
Multiple children Ensures preorder visits leftmost children first
Deep nested children Confirms correct traversal order in complex tree

Edge Cases

Empty tree: The tree has no nodes. Without handling root = None, the algorithm would throw an error when attempting to access attributes. Both Python and Go solutions return an empty list for this case.

Single node tree: A tree with only the root node tests if the algorithm can handle minimal non-empty input. The algorithm correctly adds the root value and terminates.

Deep tree with height near 1000: Recursive solutions may fail due to Python's recursion limit, but the iterative stack approach can handle this safely. The stack never grows beyond the height of the tree, ensuring memory efficiency.