742. Closest Leaf in a Binary Tree

Problem Description

In this problem, you are given a binary tree and an integer k. Each node in the tree has a unique value. The goal is to find the value of the closest leaf node to the node whose value is equal to k. A leaf node is defined as a node with no children. To measure closeness to a leaf, we count the number of edges that need to be traversed to reach any leaf from the target node. The answer will be the value of the leaf node that has the smallest number of edges between it and the node valued k.

Intuition

To find the nearest leaf to a given target node, we need to check both the path from the target up to the root (in case the closest leaf is not on the subtree of the target node) and the paths in all subtrees around the target. Because the value in each node is unique, we can uniquely identify the target node.

The main idea behind the solution is to convert the binary tree into a graph representation (undirected graph) where each node has a reference to its left child, right child, and parent. Once this graph is built, we can perform a Breadth-First Search (BFS) starting from the node with value k. BFS will help us find the shortest path to the nearest leaf, as it explores neighbors first before moving on to their next neighbors.

• First, we perform a Depth-First Search (DFS) to build the graph with all connections (including the parent-child relationship, which is not inherently present in the binary tree structure). During the DFS, we also record the node which has the value of k.

• After that, we start our BFS from the target node and check each node. If we find a node that is a leaf (no children), we return the value of that node as it is the closest leaf to our target. With BFS, as soon as we encounter a leaf, it is guaranteed to be the closest one because BFS finds nodes in order of increasing distance from the start node.

The reason we use these two algorithms (DFS to build the graph and BFS to find the nearest leaf) is to efficiently navigate the tree since the sizes of the subtrees can vary greatly, and the nearest leaf could be in any direction relative to the target node.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution follows a two-step approach:

1. Create a Graph Representation of the Tree: We define a Depth-First Search (DFS) function that will iterate through the tree nodes starting from the given root and create an undirected graph (g) where each node points to its adjacent nodes (children and parent). This is done by using a defaultdict from Python's collections module to store lists of adjacent nodes for every node we visit.

   • During the DFS traversal:

     • If the current node is not None, we add the current node to the graph pointing to its parent, and the parent pointing back to the current node.
     • We call DFS recursively for both left and right children of the current node, moving down the tree and passing the current node as the new 'parent'.

   • The DFS function achieves two goals: forming the graph and identifying the node with value k, which acts as our starting node.

2. Find the Closest Leaf Using BFS: After transforming the tree into a graph, we use a Breadth-First Search (BFS) to find the nearest leaf node to the node with value k.

   • We initialize a double-ended queue (deque) with the node of value k.
   • We also maintain a set (seen) to keep track of the visited nodes to avoid revisiting them.
   • While the queue is not empty, we continually pop nodes from the left of the queue.
   • For each popped node, we check if it's a leaf node (no children); if it is, we return its value, as this is the closest leaf node to k.
   • If the node is not a leaf, we add all unvisited adjacent nodes (from our graph) to the queue and mark the current node as seen.

   An example of the key data structures initialized in the code:

   1g = defaultdict(list)
   2q = deque([node for node in g if node and node.val == k])
   3seen = set()

   • Through BFS, the first leaf node reached from the node with value k will be the closest because BFS guarantees that we explore nodes level by level, starting from the starting node.

The combination of DFS to create the graph and BFS to find the shortest path to a leaf ensures an efficient traversal and accurate identification of the nearest leaf.

Here's the Python code that outlines this process:

1# Inside the Solution class from the provided code
2def findClosestLeaf(self, root: TreeNode, k: int) -> int:
3    def dfs(root, p):  # DFS to create the graph
4        if root:
5            g[root].append(p)
6            g[p].append(root)
7            dfs(root.left, root)
8            dfs(root.right, root)
9
10    g = defaultdict(list)  # Graph to represent the [tree](/problems/tree_intro)
11    dfs(root, None)  # Start DFS to build the graph
12    q = deque([node for node in g if node and node.val == k])  # Queue for BFS
13    seen = set()  # Set to keep track of visited nodes
14    while q:
15        node = q.popleft()
16        seen.add(node)
17        if node:
18            if node.left is None and node.right is None:  # Check for leaf
19                return node.val
20            for next in g[node]:  # Add unvisited adjacent nodes to the queue
21                if next not in seen:
22                    q.append(next)

By leveraging DFS for graph construction and BFS for the shortest path search, this solution effectively addresses the problem of finding the nearest leaf to a specified target node in a binary tree.

Example Walkthrough

Let's consider a small binary tree as an example to illustrate the solution approach:

1        1
2       / \
3      2   3
4     /   / \
5    4   5   6
6       /
7      7

And let's assume k = 2, so we are looking for the closest leaf to the node with value 2.

Step 1: Create a Graph Representation of the Tree

By applying Depth-First Search (DFS) starting at the root (node 1):

1. We visit node 1, and then its left child node 2. We add edges in our graph between 1 and 2.
2. We visit node 2's left child node 4, which is a leaf. We add edges in our graph between 2 and 4.
3. We also visit nodes 3, 5, 7, and 6 in similar fashion and add edges between each parent and its children. Node 7 is also a leaf.

After the DFS, our graph representation (g) of the tree will have these edges (considering the bi-directional nature of an undirected graph):

1g = {
2    1: [2, 3],
3    2: [1, 4],
4    3: [1, 5, 6],
5    4: [2],
6    5: [3, 7],
7    6: [3],
8    7: [5]
9}

Step 2: Find the Closest Leaf Using BFS

Starting from node with value k (which is node 2 in this example):

1. We initialize the queue with node 2. Our q looks like this: deque([2]).
2. We also initialize an empty set seen to keep track of visited nodes.
3. The BFS begins by checking node 2. Since it isn't a leaf, we add its unvisited neighbors (1 and 4) to the queue. Our seen set now contains 2, and q is now deque([1, 4]).
4. Next, we pop node 1 from the queue. It's not a leaf, so its unvisited neighbors (3) are added to the queue. q is now deque([4, 3]) and seen is {1, 2}.
5. Now, we pop node 4 from the queue. Node 4 is a leaf, so we can immediately return its value, which is 4. This is our answer, since a leaf is the node with no children, and using BFS ensures it's the closest one.

Thus, the value 4 is returned, indicating that the closest leaf to the node with value 2 is the leaf node with value 4.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(N) where N is the number of nodes in the binary tree. This is because the dfs function traverses each node exactly once to create a graph representation (g) and each edge twice (once for each direction between parent and child). The BFS loop then goes through the nodes in the graph, but each node and edge is considered only once, meaning that it can also be bounded by O(N) in the worst case when we have to visit every node once.

The space complexity is also O(N) because we store every node and its connections in the graph g, which in the worst case could have 2(N - 1) edges (for a binary tree, each parent node could have two children), closely approximating O(N) storage. There is also a seen set tracking visited nodes and a queue q for BFS, both of which could hold at most N elements in the worst-case scenario involving every node in the tree.

Learn more about how to find time and space complexity quickly using problem constraints.