Problem#
Given a binary tree where every node has a unique value , and a target key k, find the value of the nearest leaf node to target k in the tree.
Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.
In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.
Examples#
Example 1#
1
2
3
4
5
6
7
8
9
10
Input:
root = [1 , 3 , 2 ], k = 1
Diagram of binary tree:
1
/ \
3 2
Output: 2 (or 3 )
Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.
Example 2#
1
2
3
4
5
Input:
root = [1 ], k = 1
Output: 1
Explanation: The nearest leaf node is the root node itself.
Example 3#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
root = [1 ,2 ,3 ,4 ,null,null,null,5 ,null,6 ], k = 2
Diagram of binary tree:
1
/ \
2 3
/
4
/
5
/
6
Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6 ) is nearest to the node with value 2.
Constraints#
root represents a binary tree with at least 1 node and at most 1000 nodes.Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.
Solution#
Method 1 - DFS#
Reasoning and Approach#
To find the nearest leaf node to the target k, the solution requires the following steps:
Convert the Input Tree into a Graph :
Each node in the binary tree is treated as a graph node, connecting its parent and children. This essentially transforms the tree into an undirected graph.
By doing so, we can perform a Breadth-First Search (BFS) from the target node k to find the nearest leaf.
Locate the Target Node :
Traverse the binary tree while constructing the graph to locate the target node k.
Perform BFS from Target Node :
Starting from the node k, perform BFS to find the nearest leaf node (i.e., a node without children).
Code#
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public int findClosestLeaf (TreeNode root, int k) {
// Map to hold graph connections
Map< TreeNode, List< TreeNode>> graph = new HashMap<> ();
// Locate the target node
TreeNode target = buildGraph(root, null , graph, k);
// BFS to find the closest leaf
Queue< TreeNode> q = new LinkedList<> ();
Set< TreeNode> visited = new HashSet<> ();
q.add (target);
visited.add (target);
while (! q.isEmpty ()) {
TreeNode curr = q.poll ();
// Check if current node is a leaf node
if (curr.left == null && curr.right == null ) {
return curr.val ;
}
// Explore neighbours
for (TreeNode neighbour : graph.get (curr)) {
if (! visited.contains (neighbour)) {
visited.add (neighbour);
q.add (neighbour);
}
}
}
return - 1; // Should not reach here for valid input
}
private TreeNode buildGraph (TreeNode node, TreeNode parent, Map< TreeNode, List< TreeNode>> graph, int k) {
if (node == null ) return null ;
// Create connections
graph.putIfAbsent (node, new ArrayList<> ());
if (parent != null ) {
graph.get (node).add (parent);
graph.get (parent).add (node);
}
// Search for the target node
if (node.val == k) return node;
TreeNode left = buildGraph(node.left , node, graph, k);
TreeNode right = buildGraph(node.right , node, graph, k);
return left != null ? left : right;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class TreeNode :
def __init__(self, val: int = 0 , left: Optional['TreeNode' ] = None , right: Optional['TreeNode' ] = None ):
self. val = val
self. left = left
self. right = right
class Solution :
def findClosestLeaf (self, root: TreeNode, k: int) -> int:
# Dictionary to store graph connections
graph: dict[TreeNode, list[TreeNode]] = {}
# Build graph and locate target node
def dfs (node: Optional[TreeNode], parent: Optional[TreeNode]) -> Optional[TreeNode]:
if not node:
return None
if node not in graph:
graph[node] = []
if parent:
graph[node]. append(parent)
graph[parent]. append(node)
if node. val == k:
return node
left = dfs(node. left, node)
right = dfs(node. right, node)
return left or right
target = dfs(root, None )
# BFS to find the nearest leaf
queue: deque[TreeNode] = deque([target])
visited: set[TreeNode] = {target}
while queue:
curr = queue. popleft()
# Check if current node is a leaf
if not curr. left and not curr. right:
return curr. val
# Traverse neighbours
for neighbour in graph[curr]:
if neighbour not in visited:
visited. add(neighbour)
queue. append(neighbour)
return - 1 # Should not reach here for valid input
Complexity#
⏰ Time complexity: O(n)
Graph Construction : The dfs traversal constructs the graph in O(n) where n is the number of nodes in the binary tree.BFS Search : The BFS traversal visits each node at most once to locate the nearest leaf, taking O(n).Overall Complexity : O(n) + O(n) = O(n).
🧺 Space complexity: O(n)
Graph Storage : The graph uses O(n) extra space to store connections between nodes.BFS Queue and Visited Set : Both the queue and set require O(n) space in the worst case.Overall Complexity : O(n).