DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
N-ary Tree Preorder Traversal - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

"""
# 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):
            if node:
                result.append(node.val)
                for child in node.children:
                    dfs(child)
        
        dfs(root)
        return result

Complexity Analysis

Here, n is the number of nodes in the tree, and h is the height of the tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Output space is O(n) — for storing the result list.
    • Recursion stack space is O(h) — and in the worst case, h can be up to O(n) (e.g. in a skewed tree).

"""
# 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 = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                result.append(node.val)
                # Push children in reverse order so leftmost child is processed first
                for child in node.children[::-1]:
                    stack.append(child)
        return result

Complexity Analysis

Here, n is the number of nodes in the tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Output space: O(n) — for storing the result list.
    • Stack space: O(n) — In the iterative version, the stack can grow up to O(n) in the worst case (e.g., in a wide or skewed tree), because it may temporarily hold many nodes at once, especially when a node has multiple children (unlike the recursive version, where the call stack is limited to the tree height).