589. N-ary Tree Preorder Traversal

This problem asks for a preorder traversal of an N-ary tree. Preorder traversal means visiting the root node first, then recursively traversing its children from left to right.

Solutions

Two approaches are presented: recursion and iteration using a stack.

Solution 1: Recursion

This is the most straightforward approach. The recursive function dfs visits a node, adds its value to the result list, and then recursively calls itself for each child.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂(N).

Code (Python):

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
 
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node):
            if node:
                ans.append(node.val)
                for child in node.children:
                    dfs(child)
        dfs(root)
        return ans
 

The code in other languages (Java, C++, Go, TypeScript, C) follows a similar recursive structure.

Solution 2: Iteration (Stack)

This approach uses a stack to simulate the recursive calls. The root is pushed onto the stack. The loop continues as long as the stack is not empty. Each iteration pops a node, adds its value to the result, and pushes its children onto the stack in reverse order (to maintain left-to-right traversal).

Time Complexity: O(N), same as the recursive approach. Each node is visited and processed once.

Space Complexity: O(W), where W is the maximum width of the tree. In the worst-case scenario (a very wide tree), W could approach N. In the best-case scenario (a very narrow or balanced tree), W would be much smaller than N. It is still considered O(N) in the worst case.

Code (Python):

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ans.append(node.val)
                stack.extend(node.children[::-1]) # Reverse order to maintain left-to-right
        return ans

Again, the iterative approach is implemented similarly in other languages, using stack data structures appropriate for each language (e.g., Deque in Java, stack in C++).

In Summary:

Both recursive and iterative solutions have a time complexity of O(N). The recursive solution has a space complexity of O(H) (height of the tree), while the iterative solution has a space complexity of O(W) (maximum width of the tree). The choice between them depends on the specific characteristics of the input trees and the coding style preference. For very deep, narrow trees, recursion might be slightly more efficient in space. For very wide trees, the iterative approach might be preferred. For most cases, the difference is negligible.