Problem Description

You are given a binary tree where every node has a unique value, and you need to find the value of the nearest leaf node to a target value k.

The problem asks you to:

1. Start from a node with value k in the tree
2. Find the leaf node that can be reached with the minimum number of edges from this starting node
3. Return the value of that nearest leaf node

Key definitions:

• A leaf node is a node that has no children (both left and right children are null)
• Nearest to a leaf means the shortest path (minimum number of edges) needed to travel from the target node to reach any leaf
• The path can go through parent nodes, not just downward to children

For example, if you have a target node k in the middle of the tree, the nearest leaf might be:

• A leaf in the subtree below the target node
• A leaf that requires going up to parent nodes and then down another branch
• The target node itself (if k is already a leaf)

The solution approach converts the tree into an undirected graph to allow traversal in any direction (up to parents or down to children), then uses BFS from the target node k to find the nearest leaf. The first leaf encountered during the BFS traversal will be the nearest one due to the level-by-level nature of BFS.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While the input is a binary tree, the problem requires finding the shortest path to a leaf from a target node. The path can go through parent nodes (not just children), which means we need to treat the tree as an undirected graph where edges can be traversed in both directions.

Is it a tree?

• Yes: The original structure is a binary tree, and even when we convert it to an undirected graph for traversal purposes, it maintains tree properties (connected, acyclic).

DFS

• Yes: We use DFS to traverse the tree and build the undirected graph representation. This allows us to establish parent-child relationships in both directions.

Additional Consideration - Shortest Path: After using DFS to build the graph, we need to find the shortest path from the target node k to any leaf. While not explicitly shown in this flowchart path, the problem then requires:

• BFS: After constructing the graph with DFS, we use BFS starting from node k to find the nearest leaf, as BFS explores nodes level by level and guarantees finding the shortest path in an unweighted graph.

Conclusion: The flowchart correctly leads us to use DFS for the initial tree traversal and graph construction. The complete solution uses a hybrid approach: DFS for graph building, followed by BFS for finding the nearest leaf node from the target.

Intuition

The key insight is recognizing that finding the nearest leaf from a target node in a binary tree requires considering paths that go upward (to parent nodes) as well as downward (to children). In a standard tree representation, we can only traverse downward from parent to child, which limits our search space.

Consider a scenario where the target node k is deep in the left subtree, but there's a leaf node just two edges away through its parent and the parent's right child. If we only search downward from k, we might find a leaf that's much farther away in k's subtree.

This limitation leads us to transform the problem: instead of working with a tree where we can only go down, we need a structure that allows bidirectional movement. By converting the tree into an undirected graph, we can traverse from any node to its adjacent nodes (parent, left child, right child).

Once we have this graph representation, finding the nearest leaf becomes a shortest path problem in an unweighted graph. BFS is the natural choice here because:

1. It explores nodes level by level, ensuring we find the shortest path first
2. The first leaf node we encounter during BFS traversal is guaranteed to be the nearest one
3. We don't need complex distance calculations since all edges have equal weight (1)

The DFS phase builds our graph by establishing bidirectional connections between nodes, while the BFS phase efficiently finds the nearest leaf by radiating outward from the target node k until hitting a leaf node (identified by having no children: node.left == node.right == None).

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a two-phase approach: graph construction using DFS, followed by shortest path finding using BFS.

Phase 1: Graph Construction with DFS

We start by building an undirected graph representation of the tree using a recursive DFS traversal:

1. Initialize a graph g using defaultdict(list) where each node maps to its list of adjacent nodes
2. The dfs function takes two parameters: the current node (root) and its parent node (fa)
3. For each node, we add bidirectional edges:
   • Add the parent to the current node's adjacency list: g[root].append(fa)
   • Add the current node to the parent's adjacency list: g[fa].append(root)
4. Recursively process left and right children, passing the current node as their parent

This creates an undirected graph where each node can reach its parent and children directly.

Phase 2: Finding Nearest Leaf with BFS

Once the graph is built, we use BFS to find the nearest leaf from the target node k:

1. Initialize a queue q with the target node (found by checking node.val == k)
2. Maintain a visited set vis to avoid revisiting nodes
3. Process nodes level by level from the queue:
   • Dequeue a node
   • Check if it's a leaf using the condition node.left == node.right (both are None for leaves)
   • If it's a leaf, return its value immediately (guaranteed to be the nearest due to BFS)
   • Otherwise, add all unvisited adjacent nodes to the queue

Key Implementation Details:

• The graph includes None as a node (representing the parent of root), but we filter it out when needed
• The leaf check node.left == node.right is a concise way to verify both children are None
• The while 1 loop continues indefinitely because we're guaranteed to find a leaf (every tree has at least one leaf)
• BFS ensures the first leaf encountered is the closest one, as it explores nodes in order of increasing distance from the starting point

The time complexity is O(n) for both DFS traversal and BFS in the worst case, where n is the number of nodes. The space complexity is O(n) for storing the graph and visited set.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Consider this binary tree with target k = 2:

       1
      / \
     2   3
    /
   4
  / \
 5   6

Phase 1: Building the Graph with DFS

Starting from root (node 1) with parent None:

• Process node 1: Add edges 1 ↔ None
• Recursively process left child (node 2) with parent 1:
  • Add edges 2 ↔ 1
  • Process node 4 with parent 2:
    • Add edges 4 ↔ 2
    • Process node 5 with parent 4: Add edges 5 ↔ 4
    • Process node 6 with parent 4: Add edges 6 ↔ 4
• Recursively process right child (node 3) with parent 1:
  • Add edges 3 ↔ 1

Resulting graph adjacency list:

None: [1]
1: [None, 2, 3]
2: [1, 4]
3: [1]
4: [2, 5, 6]
5: [4]
6: [4]

Phase 2: BFS from Target Node k = 2

Starting BFS from node 2:

• Initialize: queue = [node_2], visited = {node_2}

• Level 0: Process node 2

  • Is it a leaf? No (has left child 4)
  • Add unvisited neighbors to queue: [node_1, node_4]
  • Mark as visited: {node_2, node_1, node_4}

• Level 1: Process node 1

  • Is it a leaf? No (has children)
  • Add unvisited neighbor node 3 to queue: [node_4, node_3]
  • Mark as visited: {node_2, node_1, node_4, node_3}

• Level 1 (continued): Process node 4

  • Is it a leaf? No (has children)
  • Add unvisited neighbors node 5 and node 6 to queue: [node_3, node_5, node_6]
  • Mark as visited: {node_2, node_1, node_4, node_3, node_5, node_6}

• Level 2: Process node 3

  • Is it a leaf? Yes! (no children)
  • Return value: 3

The algorithm finds that node 3 is the nearest leaf to target node 2, requiring only 2 edges (2 → 1 → 3). Even though nodes 5 and 6 are also leaves, they would require 3 edges (2 → 4 → 5/6), making node 3 the correct answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main phases:

1. DFS traversal to build the graph: The dfs function visits each node exactly once to construct an undirected graph representation of the tree. This takes O(n) time where n is the number of nodes.

2. BFS traversal to find the closest leaf: Starting from the node with value k, the algorithm performs a BFS traversal. In the worst case, BFS visits all nodes in the graph exactly once (each node is added to vis set only once and processed only once). This also takes O(n) time.

Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The space usage includes:

1. Graph representation (g): The defaultdict stores adjacency lists for the undirected graph. Each edge is stored twice (once for each direction), and there are n-1 edges in a tree, resulting in 2(n-1) entries. Additionally, the root has a connection to None. This uses O(n) space.

2. BFS queue (q): In the worst case, the queue can contain O(n) nodes.

3. Visited set (vis): This set can contain up to n nodes in the worst case, using O(n) space.

4. Recursion stack for DFS: The recursive dfs function can go as deep as the height of the tree, which is O(n) in the worst case (skewed tree).

The total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Leaf Node Detection

One of the most common pitfalls is incorrectly identifying leaf nodes during the BFS traversal. The code uses node.left == node.right to check if both children are None, but this relies on the assumption that the node is valid and not None itself.

The Problem:

• When building the graph, None is added as a node (representing parent of root)
• During BFS, if None gets processed from the queue, checking None.left will cause an AttributeError
• The current code partially handles this with if current_node: but doesn't properly filter None from being added to the queue in subsequent iterations

Solution:

# BFS to find the closest leaf node
while queue:
    current_node = queue.popleft()
  
    # Skip None nodes entirely
    if not current_node:
        continue
  
    # Check if current node is a leaf
    if current_node.left is None and current_node.right is None:
        return current_node.val
  
    # Explore all neighbors, filtering out None
    for neighbor in graph[current_node]:
        if neighbor and neighbor not in visited:  # Added None check
            visited.add(neighbor)
            queue.append(neighbor)

2. Target Node Not Found

The code assumes the target value k exists in the tree, but if it doesn't, the initial queue will be empty, leading to an error when trying to popleft() from an empty deque.

Solution:

# Find the starting node with value k
start_nodes = [node for node in graph if node and node.val == k]
if not start_nodes:
    # Handle case where k doesn't exist in tree
    # Could return -1, raise exception, or handle as needed
    return -1  

queue = deque(start_nodes)

3. Memory Inefficiency with Graph Storage

The graph stores bidirectional edges for every parent-child relationship, including edges to/from None. This creates unnecessary memory overhead and complicates traversal logic.

Better Approach:

def build_graph(node: Optional[TreeNode], parent: Optional[TreeNode]) -> None:
    if not node:
        return
  
    # Only add edges between actual nodes (exclude None parent for root)
    if parent:
        graph[node].append(parent)
        graph[parent].append(node)
  
    # Still need to handle root's children
    if node.left:
        graph[node].append(node.left)
        graph[node.left].append(node)
    if node.right:
        graph[node].append(node.right)
        graph[node.right].append(node)
  
    build_graph(node.left, node)
    build_graph(node.right, node)

This approach avoids adding None to the graph entirely, simplifying the BFS logic and reducing memory usage.