#589

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

N-ary Tree Preorder Traversal

Solve the N-ary Tree Preorder Traversal problem using depth-first search and stack-based traversal methods.

Problem Statement

Given the root of an N-ary tree, return the preorder traversal of its nodes' values. In a preorder traversal, each node is processed before its children, with the root node processed first. The N-ary tree is serialized in level order, with null separating groups of children.

You need to design an algorithm to traverse this tree and return the correct sequence of node values in a preorder fashion. Make sure your solution handles various tree structures, including those with deep levels and multiple child nodes at each level.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The height of the n-ary tree is less than or equal to 1000.

Solution Approach

Use a Stack for DFS Traversal

The solution starts by initializing a stack with the root node. Nodes are processed by popping from the stack, pushing their children onto the stack in reverse order to maintain the correct traversal order. This simulates depth-first traversal and ensures nodes are visited from root to leaf.

Iterate Through the Tree

Traverse the tree iteratively by visiting the node, adding its value to the result list, and then pushing its children onto the stack. The iteration continues until all nodes are processed, which ensures the preorder traversal is achieved.

Handle Empty Trees and Null Values

When the tree is empty (i.e., the root is null), the result should be an empty list. The algorithm should also correctly handle null values, which are used to separate child nodes in the input structure.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n), where n is the number of nodes in the tree. Each node is visited once. The space complexity is O(m), where m is the maximum number of nodes in the stack, which occurs at the deepest level of the tree.

What Interviewers Usually Probe

Assess the candidate's understanding of depth-first search and stack manipulation.
Evaluate how well the candidate manages tree traversal and stack management under constraints.
Check for the candidate's ability to handle edge cases like empty trees or null nodes.

Common Pitfalls or Variants

Common pitfalls

Mismanagement of stack operations leading to incorrect node order during traversal.
Failure to handle empty trees or null child nodes.
Over-complicating the solution with unnecessary recursion or additional data structures.

Follow-up variants

Implement the same traversal using recursion instead of a stack.
Modify the approach to handle different N-ary tree traversal patterns, such as postorder or level-order.
Adapt the solution to return only the first k nodes from the traversal.

FAQ

What is the primary pattern used in the N-ary Tree Preorder Traversal?

The main pattern is binary-tree traversal using a stack and depth-first search (DFS) to manage the traversal state.

How can I handle an empty tree in this problem?

If the root is null, simply return an empty list as the result.

What should I do if the tree has multiple children per node?

Ensure that children are pushed onto the stack in reverse order to maintain the correct traversal order.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of nodes in the tree, since each node is visited exactly once.

Can I use recursion for N-ary Tree Preorder Traversal?

Yes, recursion can be used, but an iterative solution using a stack is often preferred for its non-recursive nature.

terminal

Solution

Solution 1: Recursion

We can recursively traverse the entire tree. For each node, we first add the node's value to the answer, then recursively call the function for each of the node's children.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

"""
# 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]:
        def dfs(root):
            if root is None:
                return
            ans.append(root.val)
            for child in root.children:
                dfs(child)

        ans = []
        dfs(root)
        return ans

Solution 2: Iteration (Stack Implementation)

We can also solve this problem iteratively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

"""
# 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]:
        def dfs(root):
            if root is None:
                return
            ans.append(root.val)
            for child in root.children:
                dfs(child)

        ans = []
        dfs(root)
        return ans

Continue Practicing

#590 n ary tree postorder traversal #341 flatten nested list iterator #897 increasing order search tree