NUMBER OF GOOD LEAF NODE PAIRS | PYTHON | LEETCODE # 1530

In this video we are solving a popular ByteDance interview question: Number of Good Leaf Node Pairs.
This is an annoying question that is a bit tricky to solve. It uses a postorder DFS traversal and requires some interesting processing on each node to derive the solution.

[@haitaoy]

space is N, time should be n cube for your solution, as it's n square for each non-leaf nodes, i.e. n * n2 = n3.

[@forsakengod6668]

thank you

[@vijethkashyap151]

Great explanation! Thanks a lot

[@FullStackFast]

Why do we use post order instead of in order traversal?

[@byrdofafeather3184]

This isn't a Binary Search Tree, it's a binary tree, there's not concept of in-order traversal in this case.

[@ravirajshelar250]

Because, in post order we first travel the leaf nodes then the parents, that is what we wanted since we have to return the list to the parent.

[@YT.Nikolay]

I could not solve this problem, I came for help, teach me! P.S. I overcomplicated, I built an undirected graph and then it failed in case [1,1,1] :D code below
def countPairs(self, root: TreeNode, distance: int) -> int:
def traverse(node: TreeNode):
if not node:
return
if node.left:
graph[node.left.val].append(node.val)
graph[node.val].append(node.left.val)
traverse(node.left)
if node.right:
graph[node.right.val].append(node.val)
graph[node.val].append(node.right.val)
traverse(node.right)
if node.left is None and node.right is None:
q.append((node.val, 0))
graph = defaultdict(list)
q = deque() # node, steps
traverse(root)
result = 0
visited = set()
while q:
for _ in range(len(q)):
node, steps = q.popleft()
for nei in graph[node]:
if nei in visited or steps + 1 > distance:
continue
visited.add(nei)
if len(graph[nei]) == 1:
result += 1
else:
q.append((nei, steps + 1))
return result // 2 if result != 0 else 0