Closest Leaf in a Binary Tree solution and explanation
5 more videos on this problem
花花酱 LeetCode 742. Closest Leaf in a Binary Tree - 刷题找工作 EP131Hua Hua · 10:04 · 4K views
Leetcode 742 Closest Leaf in a Binary Tree - Java Solution using DFS & BFSAlgorithmicIQ · 19:01 · 1K views
Leetcode 742. Closest Leaf in a Binary Tree (tree to graph)LetsCode · 10:50 · 516 views
Problem #742 - Closest Leaf in a Binary TreeHaoTheCoder · 20:30 · 171 views
LeetCode 742 JavaHow we live in Texas · 5:01 · 57 views
LeetCode 742: Closest Leaf in a Binary TreeAlitaCode · 28:53 · 24 views
The problem
Given the root of a binary tree where every node has a unique value and a target integer k, return the value of the nearest leaf node to the target k in the tree.
Nearest to a leaf means the least number of edges traveled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.
Example 1:
Input: root = [1,3,2], k = 1 Output: 2 Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.
Example 2:
Input: root = [1], k = 1 Output: 1 Explanation: The nearest leaf node is the root node itself.
Example 3:
Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 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:
- The number of nodes in the tree is in the range
[1, 1000]. 1 <= Node.val <= 1000- All the values of the tree are unique.
- There exist some node in the tree where
Node.val == k.
Approach overview
Problem Overview: You are given a binary tree and a target node value k. The goal is to return the value of the leaf node that is closest to that target. Distance is measured by the number of edges. The challenge is that the closest leaf may not be in the target’s subtree—it could be reached by moving up to a parent and then down another branch.
Approach 1: Brute Force DFS from Every Node (O(n^2) time, O(h) space)
A straightforward idea is to treat every node as a possible starting point and compute the distance to all leaf nodes using Depth-First Search. First locate the node with value k. Then repeatedly traverse possible paths while measuring distance until a leaf is reached. Because a binary tree normally doesn't store parent pointers, each traversal may require searching portions of the tree again to move upward or across branches. In the worst case you end up exploring most nodes multiple times, leading to O(n^2) time. This approach is mainly useful for reasoning about the problem but rarely acceptable in interviews.
Approach 2: Convert Tree to Graph + BFS (O(n) time, O(n) space)
The key insight: once you allow movement to a parent, the binary tree behaves like an undirected graph. Build an adjacency list where each node connects to its left child, right child, and parent. You can construct this graph with a single DFS traversal of the Binary Tree. After building the graph, start a Breadth-First Search from the node with value k. BFS guarantees the first leaf node you encounter is the closest one because nodes are visited in increasing distance order. A leaf is simply a node with no children in the original tree. This approach processes each node at most once, resulting in O(n) time and O(n) space for the adjacency structure and queue.
Approach 3: DFS Parent Mapping + BFS from Target (O(n) time, O(n) space)
A common optimization avoids building a full adjacency list. Instead, perform a DFS to record only the parent of each node in a hash map while also locating the node with value k. During the BFS phase, each node can expand to three neighbors: left, right, and parent[node]. Maintain a visited set to prevent cycling back up the tree. As soon as BFS reaches a node with no children, that node is the closest leaf. This method still runs in O(n) time and uses O(n) space but reduces graph construction overhead and is the most common implementation in interview solutions.
Recommended for interviews: The DFS parent mapping combined with BFS is the expected solution. It demonstrates understanding of tree traversal, graph modeling, and shortest-path reasoning. Starting with the brute-force idea shows intuition about searching for leaves, but the optimized O(n) BFS approach proves you recognize that the tree effectively becomes an undirected graph when upward movement is allowed.
Solution
First, we use depth-first search to construct an undirected graph g, where g[node] represents the set of nodes adjacent to the node node. Then we start a breadth-first search from node k until we find a leaf node, which is the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
def dfs(root: Optional[TreeNode], fa: Optional[TreeNode]):
if root:
g[root].append(fa)
g[fa].append(root)
dfs(root.left, root)
dfs(root.right, root)
g = defaultdict(list)
dfs(root, None)
q = deque(node for node in g if node and node.val == k)
vis = set(q)
while 1:
node = q.popleft()
if node:
if node.left == node.right:
return node.val
for nxt in g[node]:
if nxt not in vis:
vis.add(nxt)
q.append(nxt)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Map<TreeNode, List<TreeNode>> g = new HashMap<>();
public int findClosestLeaf(TreeNode root, int k) {
dfs(root, null);
Deque<TreeNode> q = new LinkedList<>();
Set<TreeNode> vis = new HashSet<>(q.size());
for (TreeNode node : g.keySet()) {
if (node != null && node.val == k) {
vis.add(node);
q.offer(node);
break;
}
}
while (true) {
TreeNode node = q.poll();
if (node != null) {
if (node.left == node.right) {
return node.val;
}
for (TreeNode nxt : g.get(node)) {
if (vis.add(nxt)) {
q.offer(nxt);
}
}
}
}
}
private void dfs(TreeNode root, TreeNode fa) {
if (root != null) {
g.computeIfAbsent(root, k -> new ArrayList<>()).add(fa);
g.computeIfAbsent(fa, k -> new ArrayList<>()).add(root);
dfs(root.left, root);
dfs(root.right, root);
}
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findClosestLeaf(TreeNode* root, int k) {
unordered_map<TreeNode*, vector<TreeNode*>> g;
function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* root, TreeNode* fa) {
if (root) {
g[root].push_back(fa);
g[fa].push_back(root);
dfs(root->left, root);
dfs(root->right, root);
}
};
dfs(root, nullptr);
queue<TreeNode*> q;
unordered_set<TreeNode*> vis;
for (auto& [node, _] : g) {
if (node && node->val == k) {
q.push(node);
vis.insert(node);
}
}
while (1) {
auto node = q.front();
q.pop();
if (node) {
if (node->left == node->right) {
return node->val;
}
for (auto& nxt : g[node]) {
if (vis.count(nxt)) {
continue;
}
q.push(nxt);
vis.insert(nxt);
}
}
}
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findClosestLeaf(root *TreeNode, k int) int {
g := map[*TreeNode][]*TreeNode{}
var dfs func(*TreeNode, *TreeNode)
dfs = func(root, fa *TreeNode) {
if root != nil {
g[root] = append(g[root], fa)
g[fa] = append(g[fa], root)
dfs(root.Left, root)
dfs(root.Right, root)
}
}
dfs(root, nil)
q := []*TreeNode{}
vis := map[*TreeNode]bool{}
for node := range g {
if node != nil && node.Val == k {
q = append(q, node)
vis[node] = true
break
}
}
for {
node := q[0]
q = q[1:]
if node != nil {
if node.Left == node.Right {
return node.Val
}
for _, nxt := range g[node] {
if !vis[nxt] {
vis[nxt] = true
q = append(q, nxt)
}
}
}
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Exploration | O(n^2) | O(h) | Conceptual baseline or very small trees |
| Tree to Graph Conversion + BFS | O(n) | O(n) | General solution when modeling the tree as an undirected graph |
| DFS Parent Map + BFS | O(n) | O(n) | Most common interview approach with minimal graph construction |
Frequently asked questions
Is Closest Leaf in a Binary Tree easy or hard?
Closest Leaf in a Binary Tree is generally classified as a Medium problem. The difficulty comes from recognizing that the search must move both downward and upward, which turns the tree into an undirected graph and requires BFS to find the nearest leaf.
Closest Leaf in a Binary Tree Python/Java solution
Most implementations follow the same pattern: DFS to build a parent map, then BFS from the target node. Python typically uses a dictionary and deque, while Java implementations use HashMap and LinkedList queues. The algorithm runs in O(n) time in both languages.
How to solve Closest Leaf in a Binary Tree in O(n)?
Perform a DFS to map every node to its parent while locating the node with value k. Then run BFS starting from that node and expand to left child, right child, and parent. The first node reached that has no children is the closest leaf. Each node is processed once, resulting in O(n) time.
What is the best approach for Closest Leaf in a Binary Tree?
The best approach builds parent references with DFS and then runs BFS from the target node. BFS explores nodes level by level, so the first leaf encountered is the closest. This method visits each node at most once, giving O(n) time complexity and O(n) space.
Is Closest Leaf in a Binary Tree asked at Google/Amazon/Meta?
Closest Leaf in a Binary Tree appears in interview preparation lists for companies that focus heavily on tree and graph traversal problems, including Google, Amazon, and Meta. The problem tests converting a tree into a graph and applying BFS shortest-path logic.
What data structure is used in Closest Leaf in a Binary Tree?
The solution uses a combination of tree traversal and graph-style search. Common data structures include a hash map to store parent pointers, a queue for BFS traversal, and a visited set to avoid revisiting nodes. These structures allow efficient shortest-path exploration.
What is the time complexity of Closest Leaf in a Binary Tree?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. A DFS pass records parent relationships, and a BFS traversal from the target node explores each node at most once. Space complexity is also O(n) due to the parent map, visited set, and queue.