# 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](https://leetcode.com/problems/closest-leaf-in-a-binary-tree/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary tree root and target value `k` |
| Output | Value of the nearest leaf node |
| Leaf node | Node with no left and no right child |
| Distance | Number of edges |

Example function shape:

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

## Examples

### Example 1

```text
    1
   / \
  3   2
```

```python
k = 1
```

The leaves are:

```text
3
2
```

Both are distance `1` from node `1`.

Either leaf value may be returned.

### Example 2

```text
        1
       /
      2
     /
    3
   /
  4
```

```python
k = 2
```

The only leaf is:

```text
4
```

Distance from `2` to `4` is:

```text
2
```

So the answer is:

```python
4
```

### Example 3

```text
        1
       / \
      2   3
         /
        4
```

```python
k = 2
```

Node `2` is already a leaf.

So the answer is:

```python
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:

```text
        1
       / \
      2   3
         /
        4
```

Suppose:

```python
k = 3
```

The closest leaf is `4`.

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

Example:

```text
        1
       / \
      2   3
     /
    4
```

For:

```python
k = 2
```

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

So we must allow movement:

```text
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:

```text
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:

```text
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Build the graph once and visit each node at most once |
| Space | `O(n)` | Store graph edges, queue, and visited set |

## Implementation

```python
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:

```python
graph = defaultdict(list)
```

Each tree node maps to its neighboring nodes.

The DFS builds bidirectional edges:

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

This allows upward and downward movement.

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

```python
if node.val == k:
    target = node
```

After graph construction, BFS begins from the target:

```python
queue = deque([target])
```

The visited set prevents revisiting nodes:

```python
visited = {target}
```

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

```python
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:

```python
for neighbor in graph[node]:
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Root with two leaves | Multiple equally close answers |
| Deep chain | Only one reachable leaf |
| Target already leaf | Distance `0` |
| Closest leaf outside subtree | Requires parent traversal |