LeetCode 742: Closest Leaf in a Binary Tree

Problem Restatement

We are given the root of a binary tree and an integer k.

The value k exists somewhere in the tree.

We need to return the value of the leaf node closest to the node whose value is k.

A leaf node is a node with no children.

Distance means the number of edges between nodes.

The closest leaf may be:

• inside the target node’s subtree,
• or outside the subtree through parent connections.

The official problem defines the distance as the number of edges in the shortest path between nodes. (leetcode.com)

Input and Output

Example function shape:

def findClosestLeaf(root: TreeNode, k: int) -> int:
    ...

Examples

Example 1

    1
   / \
  3   2

k = 1

The leaves are:

3
2

Both are distance 1 from node 1.

Either leaf value may be returned.

Example 2

        1
       /
      2
     /
    3
   /
  4

k = 2

The only leaf is:

4

Distance from 2 to 4 is:

2

So the answer is:

4

Example 3

        1
       / \
      2   3
         /
        4

k = 2

Node 2 is already a leaf.

So the answer is:

2

First Thought: Search Only Downward

If the closest leaf were always inside the target node’s subtree, we could simply run DFS downward from the target.

But this is not always correct.

Consider:

        1
       / \
      2   3
         /
        4

Suppose:

k = 3

The closest leaf is 4.

But in other trees, the closest leaf may require moving upward first.

Example:

        1
       / \
      2   3
     /
    4

For:

k = 2

the closest leaf is 3, which is outside the subtree of 2.

So we must allow movement:

left
right
parent

This turns the tree into an undirected graph problem.

Key Insight

A tree normally allows movement only from parent to child.

But shortest path problems need movement in both directions.

So we first convert the tree into an undirected graph.

For every edge:

parent <-> child

we add connections both ways.

Then:

1. Find the node whose value is k.
2. Start BFS from that node.
3. The first leaf reached by BFS is the closest leaf.

Why BFS?

Because BFS explores nodes in increasing order of distance.

The first leaf found must therefore have minimum distance from the target node.

Algorithm

Step 1: Build the Graph

Run DFS on the tree.

For every parent-child pair:

parent <-> child

store bidirectional edges.

Also remember the node whose value equals k.

Step 2: BFS From the Target

Create a queue initialized with the target node.

Use a visited set.

While the queue is not empty:

1. Pop one node.
2. If it is a leaf, return its value.
3. Push all unvisited neighbors into the queue.

Correctness

The graph construction preserves all tree edges in both directions. Therefore every valid path between tree nodes corresponds exactly to a path in the graph.

The BFS starts at the node whose value is k. BFS explores nodes in nondecreasing order of distance from the start node. So when BFS first reaches a leaf node, that leaf has minimum distance from the target node.

Every reachable node is eventually explored unless a closer leaf is found first. Since the tree is finite and connected, BFS must eventually reach at least one leaf.

The algorithm returns the first leaf discovered by BFS, which therefore has the shortest possible path length from the target node.

Thus the returned leaf value is correct.

Complexity

Let n be the number of nodes in the tree.

Implementation

from collections import defaultdict, deque

class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
        graph = defaultdict(list)
        target = None

        def build(node: TreeNode, parent: TreeNode | None) -> None:
            nonlocal target

            if not node:
                return

            if node.val == k:
                target = node

            if parent:
                graph[node].append(parent)
                graph[parent].append(node)

            build(node.left, node)
            build(node.right, node)

        build(root, None)

        queue = deque([target])
        visited = {target}

        while queue:
            node = queue.popleft()

            if not node.left and not node.right:
                return node.val

            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

Code Explanation

We use an adjacency list:

graph = defaultdict(list)

Each tree node maps to its neighboring nodes.

The DFS builds bidirectional edges:

graph[node].append(parent)
graph[parent].append(node)

This allows upward and downward movement.

While building the graph, we also locate the target node:

if node.val == k:
    target = node

After graph construction, BFS begins from the target:

queue = deque([target])

The visited set prevents revisiting nodes:

visited = {target}

At each BFS step, we check whether the current node is a leaf:

if not node.left and not node.right:
    return node.val

Because BFS processes nodes by shortest distance first, this is the closest leaf.

Otherwise, push all unvisited neighbors:

for neighbor in graph[node]:

Testing

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(1)
    root.left = TreeNode(3)
    root.right = TreeNode(2)

    assert s.findClosestLeaf(root, 1) in [2, 3]

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.left.left = TreeNode(4)

    assert s.findClosestLeaf(root, 2) == 4

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(4)

    assert s.findClosestLeaf(root, 2) == 2

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(4)
    root.right = TreeNode(3)

    assert s.findClosestLeaf(root, 2) == 3

    print("all tests passed")

run_tests()