Hide sidebar
leetcode/DSA courseSystem Design

Closest Leaf in a Binary Tree

TreesBFS
MediumLeetCode #742

Problem Statement

Given the `root` of a binary tree and an integer `k`, find the value of the closest leaf node to the node with value `k` in the tree.

Example

123

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

Output: 2

Algorithm Explanation

This problem can be solved by converting the tree into a graph and then performing a breadth-first search (BFS) starting from the node with value `k`.

Algorithm Steps

  • Build Graph: First, we traverse the tree and build an adjacency list representation of the tree as an undirected graph. We also need to find the starting node (the one with value `k`).
  • BFS: We start a BFS from the node with value `k`. We use a queue to keep track of the nodes to visit and a set to keep track of visited nodes to avoid cycles.
  • Find Closest Leaf: The first leaf node we encounter during the BFS will be the closest one to the starting node. A node is a leaf if it has only one connection in our graph (its parent), and it's not the root of the original tree.
123
Build Graph
Graph built from tree.

Queue

Visited

Closest Leaf in a Binary Tree Solution

from collections import defaultdict, deque

class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
        graph = defaultdict(list)
        start_node = None
        
        def build_graph(node, parent):
            nonlocal start_node
            if not node:
                return
            if node.val == k:
                start_node = node
            
            if parent:
                graph[node].append(parent)
                graph[parent].append(node)
            
            build_graph(node.left, node)
            build_graph(node.right, node)
            
        build_graph(root, None)
        
        queue = deque([start_node])
        visited = {start_node}
        
        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)
        
        return -1 # Should not be reached