LeetCode Solutions Blog

Closest Leaf in a Binary Tree

Number: 743

Difficulty: Medium

Paid? Yes

Problem Description

Given the root of a binary tree with unique values and a target integer k, find and return the value of the nearest leaf node to the target k. The "nearest" is defined in terms of the minimum number of edges traveled from the target node until a leaf node is reached. A leaf is any node with no children.

Key Insights

Convert the binary tree into an undirected graph to allow traversal in all directions (to parent and children).
Use depth-first search (DFS) to build the graph and simultaneously identify which nodes are leaves (nodes with no left and right children in the tree).
Locate the target node (node with value k) during DFS.
Perform a breadth-first search (BFS) from the target node in the graph to find the first encountered leaf, as BFS naturally finds the shortest path in an unweighted graph.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since both DFS and BFS traverse all nodes in the worst case. Space Complexity: O(n), for storing the graph and BFS queue.

Solution

We first perform DFS on the binary tree to build a graph representation using an adjacency list. During this DFS, we also mark nodes as leaves based on whether they have any children. Once the graph is built and the target node is identified, we perform BFS from the target node. In BFS, the first node that meets the criteria of being a leaf (based on the original binary tree structure) is returned immediately. This approach guarantees that the path found is the shortest in terms of the number of edges traveled.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def findClosestLeaf(root: TreeNode, k: int) -> int:
    from collections import defaultdict, deque
    
    # graph will map each node to its list of neighboring nodes.
    graph = defaultdict(list)
    # leaf_map will mark if a node is a leaf in the original tree.
    leaf_map = {}
    target_node = None

    # Helper DFS function to build the graph.
    def dfs(node, parent):
        nonlocal target_node
        if not node:
            return
        
        if node.val == k:
            target_node = node
        
        # Determine if node is a leaf (no children in the original tree).
        if not node.left and not node.right:
            leaf_map[node] = True
        else:
            leaf_map[node] = False
        
        if parent:
            graph[node].append(parent)
            graph[parent].append(node)
        if node.left:
            dfs(node.left, node)
        if node.right:
            dfs(node.right, node)
    
    dfs(root, None)
    
    # BFS initialization from target node.
    queue = deque([target_node])
    visited = set([target_node])
    
    while queue:
        current = queue.popleft()
        # Check if our current node is a leaf in the original tree.
        if leaf_map[current]:
            return current.val
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return -1  # Should not be reached as per constraints
    
# Line-by-line comments provided in the code.