Closest Leaf in a Binary Tree

Closest Leaf in a Binary Tree

What is this problem about?

The Closest Leaf in a Binary Tree interview question asks you to find the leaf node that is closest to a given target node k. A leaf node is defined as a node with no children. The "distance" is the number of edges in the shortest path between the target node and the leaf. This is tricky because the closest leaf might be in the target node's own subtree, or it might be reachable by going up through a parent and then down into a different subtree.

Why is this asked in interviews?

Databricks, LinkedIn, and Amazon use this Tree interview pattern to test your ability to convert a tree into a graph. Trees are directed (parent to child), but finding the "closest" node often requires moving in any direction (including child to parent). It tests your knowledge of Breadth-First Search (BFS) and tree-to-graph transformation.

Algorithmic pattern used

The standard approach is a two-step process:

1. Graph Transformation: Use Depth-First Search (DFS) to traverse the tree and build an adjacency list (or map nodes to their parents) so you can move upwards.
2. Breadth-First Search (BFS): Starting from the target node k, perform a BFS. The first leaf node you encounter in the BFS will be the closest one.

Example explanation

Consider a tree where:

• 1 is the root.
• 1 has children 2 and 3.
• 2 has child 4 (leaf).
• 3 has children 5 and 6 (leaves). Target node: 3.

1. In the graph version, 3 is connected to 1 (parent), 5 (child), and 6 (child).
2. BFS starts at 3.
3. Level 1: Check 5 and 6. Both are leaves!
4. The closest distance is 1. We can return either 5 or 6. If the leaf 4 was closer through the parent 1, the BFS would have found it if it reached that level first.

Common mistakes candidates make

• Searching only subtrees: Only looking for leaves below the target node and forgetting that a leaf could be "above" it in the original tree structure.
• No Visited Set: Forgetting to use a visited set in BFS after converting the tree to an undirected graph, leading to infinite cycles.
• Target not found: Not properly handling the case where the target node k is not present in the tree (though usually guaranteed to exist).

Interview preparation tip

Whenever you need to find the "shortest path" in a tree that allows moving to parents, immediately think of BFS on an undirected graph representation of the tree.