Closest Leaf in a Binary Tree - Solution & Explanation

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.