All Traversals¶

Depth First Search¶

589. N-ary Tree Preorder Traversal (Easy)¶

def preorder(self, root: "Node") -> List[int]:
    def recursion(node: "Node"):
        nonlocal ans
        if node:
            ans.append(node.val)
            for child in node.children:
                recursion(child)

    ans = []
    recursion(root)
    return ans

def preorder(self, root: "Node") -> List[int]:
    arr = []
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                arr.append(node.val)
            else:
                for child in node.children[::-1]:
                    if child:
                        stack.append((child, False))
                stack.append((node, True))
    return arr

590. N-ary Tree Postorder Traversal (Easy)¶

def postorder(self, root: "Node") -> List[int]:
    def recursion(node: "Node"):
        nonlocal ans
        if node:
            for child in node.children:
                recursion(child)
            ans.append(node.val)

    ans = []
    recursion(root)
    return ans

def postorder(self, root: "Node") -> List[int]:
    arr = []
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                arr.append(node.val)
            else:
                stack.append((node, True))
                for child in node.children[::-1]:
                    if child:
                        stack.append((child, False))
    return arr

Breadth First Search / Level Order¶

429. N-ary Tree Level Order Traversal (Medium)¶

def levelOrder(self, root: "Node") -> List[List[int]]:
    q = [root]
    ans = []
    while q:
        mini_q = []
        mini_ans = []
        while q:
            node = q.pop(0)
            if node:
                mini_ans.append(node.val)
                for child in node.children:
                    if child:
                        mini_q.append(child)
        q = mini_q
        ans.append(mini_ans) if mini_ans else None
    return ans

def levelOrder(self, root: "Node") -> List[List[int]]:
    def recursion(node):
        nonlocal cur_depth
        if node:
            cur_depth += 1
            hm[cur_depth].append(node.val)
            for child in node.children:
                recursion(child)
            cur_depth -= 1

    cur_depth = 0
    hm = defaultdict(list)
    recursion(root)
    return list(hm.values())