LeetCode 742 - Closest Leaf in a Binary Tree

The problem asks us to find the closest leaf node to a given target node k in a binary tree. The input is the root of a binary tree where each node has a unique integer value. A leaf node is defined as any node without children.

leetcodemediumtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 742

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to find the closest leaf node to a given target node k in a binary tree. The input is the root of a binary tree where each node has a unique integer value. A leaf node is defined as any node without children. The output is the value of the leaf node that can be reached from the target node k by traversing the fewest number of edges.

The input tree is guaranteed to have at least one node (1 <= number of nodes <= 1000), all values are unique (1 <= Node.val <= 1000), and the target node k exists in the tree. This guarantees that we do not need to handle empty trees or missing target values.

Important edge cases include when the tree consists of only the root node, in which case the root itself is a leaf and the closest leaf to itself. Another tricky scenario is when the nearest leaf is not in the subtree rooted at the target node, but rather higher up in the tree (requiring traversal through the parent node).

Approaches

Brute Force Approach

A naive approach is to first locate the target node k, then perform a breadth-first search (BFS) or depth-first search (DFS) to every leaf in its subtree to find the closest one. If the nearest leaf happens to be outside the target node's subtree (i.e., above in the tree), we would need to explore all paths to leaves from every ancestor of the target node, which would require extra bookkeeping. This is possible but inefficient, especially when the tree is large and unbalanced, because we may explore many unnecessary paths.

Key Insight for Optimal Approach

The problem becomes much simpler if we allow traversal from a node to its parent as well as its children. If we convert the tree into an undirected graph, where each node is connected to its children and its parent, finding the nearest leaf from the target node is equivalent to finding the shortest path from the target node to any leaf in this graph. We can then use BFS starting from the target node to guarantee we find the closest leaf in the fewest steps.

This approach handles leaves in the subtree of the target and leaves outside the subtree in the same unified framework.

Comparison Table

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Search all paths from target to leaves; inefficient for unbalanced trees
Optimal O(n) O(n) Convert tree to graph and use BFS from target node

Algorithm Walkthrough

  1. Map Parent Pointers: Traverse the tree using DFS and store a mapping from each node to its parent. This allows traversal from child to parent during BFS.
  2. Identify Leaf Nodes: A node is a leaf if it has no children. During BFS, if a node has no children, we immediately return its value.
  3. Start BFS from Target Node: Using the parent mapping, enqueue the target node. Use a set to track visited nodes to prevent cycles.
  4. Explore Neighbors: For each node dequeued from BFS, consider its left child, right child, and parent (if they exist and are unvisited). Enqueue them for further exploration.
  5. Return First Leaf: BFS ensures the first leaf encountered is the closest, because BFS explores nodes in order of increasing distance from the target.

Why it works: BFS guarantees the shortest path in an unweighted graph. By including the parent in traversal, we correctly consider leaves that are closer but not in the target’s subtree.

Python Solution

# 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
from collections import deque
from typing import Optional

class Solution:
    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        parent = {}

        # Step 1: DFS to map parents and find target node
        def dfs(node, par=None):
            if not node:
                return None
            if par:
                parent[node] = par
            if node.val == k:
                target_node[0] = node
            dfs(node.left, node)
            dfs(node.right, node)

        target_node = [None]
        dfs(root)

        # Step 2: BFS from target node
        queue = deque([target_node[0]])
        visited = set([target_node[0]])

        while queue:
            node = queue.popleft()
            # If leaf node, return its value
            if not node.left and not node.right:
                return node.val
            for neighbor in (node.left, node.right, parent.get(node)):
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

Implementation Walkthrough: First, a DFS maps each node to its parent and identifies the target node. Then BFS explores nodes layer by layer, using the parent mapping to move upwards if necessary. The first leaf encountered in BFS is returned immediately.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findClosestLeaf(root *TreeNode, k int) int {
    parent := make(map[*TreeNode]*TreeNode)
    var targetNode *TreeNode

    // DFS to map parents and locate target node
    var dfs func(node, par *TreeNode)
    dfs = func(node, par *TreeNode) {
        if node == nil {
            return
        }
        if par != nil {
            parent[node] = par
        }
        if node.Val == k {
            targetNode = node
        }
        dfs(node.Left, node)
        dfs(node.Right, node)
    }
    dfs(root, nil)

    queue := []*TreeNode{targetNode}
    visited := make(map[*TreeNode]bool)
    visited[targetNode] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left == nil && node.Right == nil {
            return node.Val
        }
        neighbors := []*TreeNode{node.Left, node.Right, parent[node]}
        for _, neighbor := range neighbors {
            if neighbor != nil && !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    return -1
}

Go-specific notes: Go uses nil checks instead of Python’s None. Slices are used as a queue, and a map keeps track of visited nodes. The logic mirrors the Python version.

Worked Examples

Example 1: root = [1,3,2], k = 1

DFS maps parents: 3→1, 2→1. BFS starts at 1, neighbors are 3 and 2. Both 3 and 2 are leaves. BFS returns 2 (or 3) because the first leaf dequeued is returned.

Example 2: root = [1], k = 1

DFS maps no parents. BFS starts at 1, which is itself a leaf. Returns 1 immediately.

Example 3: root = [1,2,3,4,null,null,null,5,null,6], k = 2

DFS maps parents. BFS from 2: neighbors are 1 (parent) and 4 (left child). BFS explores 4, then 5 and 6. BFS explores 1 next, then 3, which is a leaf. Returns 3 as the closest leaf.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited once in DFS and once in BFS, n is number of nodes
Space O(n) Parent mapping and BFS queue use O(n) space in the worst case

Because we convert the tree into an undirected graph conceptually, BFS ensures we do not traverse more than necessary, keeping the algorithm linear in both time and space.

Test Cases

# Provided examples
assert Solution().findClosestLeaf(TreeNode(1, TreeNode(3), TreeNode(2)), 1) in [2,3]  # either leaf
assert Solution().findClosestLeaf(TreeNode(1), 1) == 1  # root is leaf
root = TreeNode(1, TreeNode(2, TreeNode(4, TreeNode(5, None, TreeNode(6)))), TreeNode(3))
assert Solution().findClosestLeaf(root, 2) == 3  # nearest leaf outside subtree

# Edge cases
assert Solution().findClosestLeaf(TreeNode(1, None, TreeNode(2)), 1) == 2  # right child leaf
assert Solution().findClosestLeaf(TreeNode(1, TreeNode(2)), 2) == 2  # target is leaf itself
Test Why
[1,3,2], k=1 Verifies BFS returns closest leaf in subtree
[1], k=1 Single-node tree edge case
Complex tree, k=2 Tests leaf outside target subtree
Right-child only tree Ensures right child leaf handled correctly
Target is leaf Ensures algorithm works when target itself is a leaf

Edge Cases

**