Skip to main content

Traversals

589. N-ary Tree Preorder Traversal​

Easy·
2 Approachesclick to switch
FIG. N ARY TREE PREORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • rec visits each of the n nodes exactly once.
Space
O(h)
  • The recursion call stack depth equals tree height h.
def preorder(self, root: "Node") -> List[int]:
def rec(node):
if not node:
return
result.append(node.val)
for child in node.children:
rec(child)
 
result = []
rec(root)
return result

590. N-ary Tree Postorder Traversal​

Easy·
2 Approachesclick to switch
FIG. N ARY TREE POSTORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • rec visits every node exactly once.
Space
O(h)
  • The recursion call stack grows to the tree's height h.
def postorder(self, root: "Node") -> List[int]:
def rec(node):
if not node:
return
for child in node.children:
rec(child)
result.append(node.val)
 
result = []
rec(root)
return result

429. N-ary Tree Level Order Traversal​

Medium·
3 Approachesclick to switch
FIG. N ARY TREE LEVEL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each node is popped off queue and visited exactly once.
Space
O(w)
  • queue holds one complete level at a time, bounded by the tree's max width w.
def levelOrder(self, root: "Node") -> List[List[int]]:
levels = []
queue = collections.deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
level.append(node.val)
for child in node.children:
queue.append(child) if child else None
if level:
levels.append(level)
return levels