Create viral videos with

GPT-4o + Ads library

Use GPT-4o to edit video empowered by Youtube & Tiktok & Facebook ads library. Turns your links or media assets into viral videos in one click.

Try it free

#Science & Technology

Hey everyone, welcome back! Let's write some more neat code today. Let's solve the problem "Number of Good Leaf Nodes Pairs", Leetcode number 1530. It's a bit of a mouthful, but we're going to break it down together.

We're given the root of a binary tree and a second parameter, which is the distance. We need to find all pairs of leaf nodes such that the shortest path between them is less than or equal to this distance.

**Leaf Node:**A node with no children.**Shortest Path:**The minimum distance between two nodes, which usually runs through their lowest common ancestor (LCA).

In the given example, the shortest path between the two leaf nodes runs through their LCA. The sum of the distances on both sides of the LCA gives the total distance.

**ExampleExplanation**:

```
For instance, [in a binary tree](https://www.topview.ai/blog/detail/a-little-secret-for-binary-tree-questions), the LCA might have a distance of 2 to one leaf and a distance of 1 to another. Adding these, the total distance would be 3. If the provided threshold is also 3, this pair is valid.
```

To solve this problem, the most intuitive approach is to use Depth-First Search (DFS) in a bottom-up manner. When we reach a non-leaf node, it should already have information about distances from its children, and it needs to combine this information to determine the shortest paths through it.

There are two solutions:

**Tree DFS with nested loops:**This may initially seem like an O(N^3) solution, but more precisely, it's O(N * D^2) where D is the second parameter (distance), and N is the number of nodes.**Efficient BFS approach:**This approach also involves transforming the problem into a graph search problem but isn't always more efficient in practice.

The main idea involves traversing from the leaf nodes upwards, combining and counting distances from left and right subtrees. This method ensures we handle pairs efficiently.

Here's the step-by-step DFS solution to find the number of good leaf node pairs:

```
from collections import defaultdict, deque
class Solution:
def countPairs(self, root, distance):
self.pairs = 0
def dfs(node):
if not node:
return defaultdict(int)
if not node.left and not node.right:
return defaultdict(int, (1: 1))
left_dist = dfs(node.left)
right_dist = dfs(node.right)
for d1 in left_dist:
for d2 in right_dist:
if d1 + d2 <= distance:
self.pairs += left_dist[d1] * right_dist[d2]
all_dists = defaultdict(int)
for d in left_dist:
if d + 1 <= distance:
all_dists[d + 1] += left_dist[d]
for d in right_dist:
if d + 1 <= distance:
all_dists[d + 1] += right_dist[d]
return all_dists
dfs(root)
return self.pairs
```

To further optimize, we use hashmaps to count the frequencies of distances, reducing the upfront need for nested loops. This drastically improves efficiency, especially for large trees with significant depths.

Another feasible approach is to treat the tree as a general graph and find shortest paths using BFS from all leaf nodes:

```
class Solution:
def countPairs(self, root, distance):
if not root:
return 0
# Build graph
graph = collections.defaultdict(list)
leaf_nodes = set()
def dfs(node):
if not node:
return
if not node.left and not node.right:
leaf_nodes.add(node)
if node.left:
graph[node].append(node.left)
graph[node.left].append(node)
dfs(node.left)
if node.right:
graph[node].append(node.right)
graph[node.right].append(node)
dfs(node.right)
dfs(root)
# BFS from leaf nodes
def bfs_leaf(node):
queue = collections.deque([(node, 0)]) # (current_node, current_distance)
visited = set([node])
count = 0
while queue:
current, dist = queue.popleft()
if dist > distance:
break
for neighbor in graph[current]:
if neighbor not in visited:
if neighbor in leaf_nodes and neighbor != node and dist + 1 <= distance:
count += 1
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return count
total_pairs = sum(bfs_leaf(leaf) for leaf in leaf_nodes)
return total_pairs // 2 # Each pair is counted twice
```

Both DFS and BFS approaches have their merits. DFS with hashmap optimizations appears more efficient based on experimental results. Happy coding!

- Binary Tree
- Leaf Nodes
- DFS (Depth-First Search)
- BFS (Breadth-First Search)
- Lowest Common Ancestor (LCA)

**Q1: What is a Leaf Node?**
A: A leaf node is a node in a binary tree which does not have any children.

**Q2: What is BFS and DFS?**
A: BFS (Breadth-First Search) and DFS (Depth-First Search) are algorithms for traversing or searching tree or graph data structures.

**Q3: What does the 'distance' parameter represent?**
A: The 'distance' parameter represents the maximum allowed distance for pairs of leaf nodes in terms of the shortest path through their lowest common ancestor.

**Q4: Why do we use a hashmap in the optimized DFS solution?**
A: The hashmap efficiently counts and manages node distances to avoid excessive nested loops, thereby reducing the time complexity.

In addition to the incredible tools mentioned above, for those looking to elevate their video creation process even further, Topview.ai stands out as a revolutionary online AI video editor.

TopView.ai provides two powerful tools to help you make ads video in one click.

Materials to Video: you can upload your raw footage or pictures, TopView.ai will edit video based on media you uploaded for you.

Link to Video: you can paste an E-Commerce product link, TopView.ai will generate a video for you.

You may also like