Simply Traverse

Height

559. Maximum Depth of N-ary Tree

Easy·

559Maximum Depth of N-ary Tree

3 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Iterative)

O(2n) timeO(n) aux

BFS (Iterative)

O(n) timeO(w) aux

FIG. MAXIMUM DEPTH OF N ARY TREE● INTERACTIVE

visualization loads as you reach it

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 Approaches · 2 patterns

Seen Set

O(2n) timeO(n) aux

Counter

O(n) timeO(n) aux

XOR↗ XOR

O(2n) timeO(1) aux

FIG. FIND ROOT OF N ARY TREE● INTERACTIVE

visualization loads as you reach it

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

---

Weighted Sum

4015. Weighted Sum of a Tree

Medium·

4015Weighted Sum of a Tree

The tree arrives as a parent array (parent[i] = -1 marks the root). Each node's weight is tree_height - depth + 1, so the shallowest nodes count for the most. Return the sum of nums[i] times its weight.

2 Approaches

BFS (Iterative)

O(4n) timeO(3n + w) aux

Memoized Parent Walk (Recursive)

O(4n) timeO(n + h) aux

FIG. WEIGHTED SUM OF A TREE● INTERACTIVE

visualization loads as you reach it

def weightedSum(self, parent: list[int], nums: list[int]) -> int:

n = len(parent)

children = {}

depths = [0] * n

for node in range(n):

par = parent[node]

if par not in children:

children[par] = set()

children[par].add(node)

queue = collections.deque([*children[-1]])

depth = 1

while queue:

for _ in range(len(queue)):

node = queue.popleft()

depths[node] = depth

if node in children:

for c in children[node]:

queue.append(c)

depth += 1

tree_height = max(depths)

ans = 0

for i in range(n):

ans += nums[i] * (tree_height - depths[i] + 1)

return ans

---