Simply Traverse

Height

559. Maximum Depth of N-ary Tree

Easy·

559Maximum Depth of N-ary Tree

3 Approachesclick to switch

1

DFS (Recursive)

O(n)

O(h)

2

DFS (Iterative)

O(n)

O(n)

3

BFS (Iterative)

O(n)

O(w)

FIG. MAXIMUM DEPTH OF N ARY TREE● 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 maxDepth(self, root: "Node") -> int:

def rec(node):

if not node:

return 0

child_max_depth = 0

for child in node.children:

child_max_depth = max(child_max_depth, rec(child))

return 1 + child_max_depth

 

return rec(root)

---

Find Root

1506. Find Root of N-Ary Tree

Medium·

1506Find Root of N-Ary Tree

3 Approachesclick to switch

1

Seen Set

O(2n)

O(n)

2

Counter

O(n)

O(n)

3

XOR

O(2n)

O(1)

FIG. FIND ROOT OF N ARY TREE● INTERACTIVE

visualization loads as you reach it

Time

O(2n)

• The first loop visits all n nodes to collect every child value into seen, and the second loop visits all n nodes again to find the one never seen as a child - two separate O(n) passes.

Space

O(n)

• seen holds up to n child values.

def findRoot(self, tree: List["Node"]) -> "Node":

seen = set()

for node in tree:

for child in node.children:

seen.add(child.val)

for node in tree:

if node.val not in seen:

return node

---