742. Closest Leaf in a Binary Tree


Problem Description

In this problem, you are given a binary tree and an integer k. Each node in the tree has a unique value. The goal is to find the value of the closest leaf node to the node whose value is equal to k. A leaf node is defined as a node with no children. To measure closeness to a leaf, we count the number of edges that need to be traversed to reach any leaf from the target node. The answer will be the value of the leaf node that has the smallest number of edges between it and the node valued k.

Intuition

To find the nearest leaf to a given target node, we need to check both the path from the target up to the root (in case the closest leaf is not on the subtree of the target node) and the paths in all subtrees around the target. Because the value in each node is unique, we can uniquely identify the target node.

The main idea behind the solution is to convert the binary tree into a graph representation (undirected graph) where each node has a reference to its left child, right child, and parent. Once this graph is built, we can perform a Breadth-First Search (BFS) starting from the node with value k. BFS will help us find the shortest path to the nearest leaf, as it explores neighbors first before moving on to their next neighbors.

  • First, we perform a Depth-First Search (DFS) to build the graph with all connections (including the parent-child relationship, which is not inherently present in the binary tree structure). During the DFS, we also record the node which has the value of k.

  • After that, we start our BFS from the target node and check each node. If we find a node that is a leaf (no children), we return the value of that node as it is the closest leaf to our target. With BFS, as soon as we encounter a leaf, it is guaranteed to be the closest one because BFS finds nodes in order of increasing distance from the start node.

The reason we use these two algorithms (DFS to build the graph and BFS to find the nearest leaf) is to efficiently navigate the tree since the sizes of the subtrees can vary greatly, and the nearest leaf could be in any direction relative to the target node.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

In a binary min heap, the maximum element can be found in:

Solution Approach

The solution follows a two-step approach:

  1. Create a Graph Representation of the Tree: We define a Depth-First Search (DFS) function that will iterate through the tree nodes starting from the given root and create an undirected graph (g) where each node points to its adjacent nodes (children and parent). This is done by using a defaultdict from Python's collections module to store lists of adjacent nodes for every node we visit.

    • During the DFS traversal:

      • If the current node is not None, we add the current node to the graph pointing to its parent, and the parent pointing back to the current node.
      • We call DFS recursively for both left and right children of the current node, moving down the tree and passing the current node as the new 'parent'.
    • The DFS function achieves two goals: forming the graph and identifying the node with value k, which acts as our starting node.

  2. Find the Closest Leaf Using BFS: After transforming the tree into a graph, we use a Breadth-First Search (BFS) to find the nearest leaf node to the node with value k.

    • We initialize a double-ended queue (deque) with the node of value k.
    • We also maintain a set (seen) to keep track of the visited nodes to avoid revisiting them.
    • While the queue is not empty, we continually pop nodes from the left of the queue.
    • For each popped node, we check if it's a leaf node (no children); if it is, we return its value, as this is the closest leaf node to k.
    • If the node is not a leaf, we add all unvisited adjacent nodes (from our graph) to the queue and mark the current node as seen.

    An example of the key data structures initialized in the code:

    1g = defaultdict(list)
    2q = deque([node for node in g if node and node.val == k])
    3seen = set()
    • Through BFS, the first leaf node reached from the node with value k will be the closest because BFS guarantees that we explore nodes level by level, starting from the starting node.

The combination of DFS to create the graph and BFS to find the shortest path to a leaf ensures an efficient traversal and accurate identification of the nearest leaf.

Here's the Python code that outlines this process:

1# Inside the Solution class from the provided code
2def findClosestLeaf(self, root: TreeNode, k: int) -> int:
3    def dfs(root, p):  # DFS to create the graph
4        if root:
5            g[root].append(p)
6            g[p].append(root)
7            dfs(root.left, root)
8            dfs(root.right, root)
9
10    g = defaultdict(list)  # Graph to represent the [tree](/problems/tree_intro)
11    dfs(root, None)  # Start DFS to build the graph
12    q = deque([node for node in g if node and node.val == k])  # Queue for BFS
13    seen = set()  # Set to keep track of visited nodes
14    while q:
15        node = q.popleft()
16        seen.add(node)
17        if node:
18            if node.left is None and node.right is None:  # Check for leaf
19                return node.val
20            for next in g[node]:  # Add unvisited adjacent nodes to the queue
21                if next not in seen:
22                    q.append(next)

By leveraging DFS for graph construction and BFS for the shortest path search, this solution effectively addresses the problem of finding the nearest leaf to a specified target node in a binary tree.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's consider a small binary tree as an example to illustrate the solution approach:

1        1
2       / \
3      2   3
4     /   / \
5    4   5   6
6       /
7      7

And let's assume k = 2, so we are looking for the closest leaf to the node with value 2.

Step 1: Create a Graph Representation of the Tree

By applying Depth-First Search (DFS) starting at the root (node 1):

  1. We visit node 1, and then its left child node 2. We add edges in our graph between 1 and 2.
  2. We visit node 2's left child node 4, which is a leaf. We add edges in our graph between 2 and 4.
  3. We also visit nodes 3, 5, 7, and 6 in similar fashion and add edges between each parent and its children. Node 7 is also a leaf.

After the DFS, our graph representation (g) of the tree will have these edges (considering the bi-directional nature of an undirected graph):

1g = {
2    1: [2, 3],
3    2: [1, 4],
4    3: [1, 5, 6],
5    4: [2],
6    5: [3, 7],
7    6: [3],
8    7: [5]
9}

Step 2: Find the Closest Leaf Using BFS

Starting from node with value k (which is node 2 in this example):

  1. We initialize the queue with node 2. Our q looks like this: deque([2]).
  2. We also initialize an empty set seen to keep track of visited nodes.
  3. The BFS begins by checking node 2. Since it isn't a leaf, we add its unvisited neighbors (1 and 4) to the queue. Our seen set now contains 2, and q is now deque([1, 4]).
  4. Next, we pop node 1 from the queue. It's not a leaf, so its unvisited neighbors (3) are added to the queue. q is now deque([4, 3]) and seen is {1, 2}.
  5. Now, we pop node 4 from the queue. Node 4 is a leaf, so we can immediately return its value, which is 4. This is our answer, since a leaf is the node with no children, and using BFS ensures it's the closest one.

Thus, the value 4 is returned, indicating that the closest leaf to the node with value 2 is the leaf node with value 4.

Not Sure What to Study? Take the 2-min Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Python Solution

1from collections import defaultdict, deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
12        # Helper function to perform Depth-First Search (DFS) to build the graph.
13        def dfs(node, parent):
14            if node:
15                # Establish parent-child relationship in both directions.
16                graph[node].append(parent)
17                graph[parent].append(node)
18                # Recursively call dfs on the left and right children.
19                dfs(node.left, node)
20                dfs(node.right, node)
21
22        # Graph representation using a dictionary with adjacency lists.
23        graph = defaultdict(list)
24        # Build the graph with None as the initial parent.
25        dfs(root, None)
26      
27        # Find the nodes that match the value k and use them as the starting points.
28        queue = deque([node for node in graph if node and node.val == k])
29        # Set to keep track of visited nodes to prevent cycles.
30        seen = set()
31        while queue:
32            current_node = queue.popleft()
33            seen.add(current_node)
34            if current_node:
35                # If we find a leaf node, return its value.
36                if current_node.left is None and current_node.right is None:
37                    return current_node.val
38                # Add all connected nodes that haven't been seen to the queue.
39                for neighbor in graph[current_node]:
40                    if neighbor not in seen:
41                        queue.append(neighbor)
42        # If no leaf is found (not expected in a valid binary tree), return None.
43        # This line is just for safety and theoretically should never be reached.
44        # In practice, the input is assumed to be a valid binary tree with at least one leaf.
45        return None
46

Java Solution

1import java.util.*;
2
3// Definition for a binary tree node is provided.
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8    TreeNode() {}
9    TreeNode(int val) { this.val = val; }
10    TreeNode(int val, TreeNode left, TreeNode right) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17class Solution {
18    // graph is used to represent the tree structure along with parent pointers.
19    private Map<TreeNode, List<TreeNode>> graph;
20
21    // Method to find the closest leaf to a node with value k in a binary tree.
22    public int findClosestLeaf(TreeNode root, int k) {
23        graph = new HashMap<>();
24        // Build the graph using Depth-First Search (DFS).
25        buildGraph(root, null);
26
27        // Queue for Breadth-First Search (BFS).
28        Deque<TreeNode> queue = new LinkedList<>();
29
30        // Initialize the BFS queue with the node of value k.
31        for (TreeNode node : graph.keySet()) {
32            if (node != null && node.val == k) {
33                queue.offer(node);
34                break;
35            }
36        }
37
38        // HashSet to keep track of visited nodes.
39        Set<TreeNode> seen = new HashSet<>();
40
41        // BFS to find the closest leaf.
42        while (!queue.isEmpty()) {
43            TreeNode currentNode = queue.poll();
44            seen.add(currentNode);
45
46            // If a leaf node is found, return its value.
47            if (currentNode.left == null && currentNode.right == null) {
48                return currentNode.val;
49            }
50
51            // Add neighboring nodes to queue if not already visited.
52            for (TreeNode neighbor : graph.get(currentNode)) {
53                if (!seen.contains(neighbor)) {
54                    queue.offer(neighbor);
55                }
56            }
57        }
58
59        // In case no leaf node is found (should not happen if tree is valid), return 0.
60        return 0;
61    }
62
63    // Helper method to build the graph with parent pointers.
64    private void buildGraph(TreeNode node, TreeNode parent) {
65        if (node != null) {
66            // Connect the node with its parent.
67            graph.computeIfAbsent(node, k -> new ArrayList<>()).add(parent);
68            // Connect the parent with the node.
69            graph.computeIfAbsent(parent, k -> new ArrayList<>()).add(node);
70
71            // Recursive DFS calls for left and right children.
72            buildGraph(node.left, node);
73            buildGraph(node.right, node);
74        }
75    }
76}
77

C++ Solution

1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
4#include <queue>
5
6// Forward declaration for TreeNode structure
7struct TreeNode {
8    int val;
9    TreeNode *left;
10    TreeNode *right;
11    TreeNode() : val(0), left(nullptr), right(nullptr) {}
12    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18    // Graph representation of the binary tree using adjacency list
19    unordered_map<TreeNode*, vector<TreeNode*>> graph;
20
21    // Convert binary tree to graph and find closest leaf to a given value k
22    int findClosestLeaf(TreeNode* root, int k) {
23        // Convert tree to graph with bidirectional edges
24        buildGraph(root, nullptr);
25
26        // Nodes to visit queue
27        queue<TreeNode*> toVisit;
28
29        // Start from the node with value k
30        for (auto& node : graph) {
31            if (node.first && node.first->val == k) {
32                toVisit.push(node.first);
33                break;
34            }
35        }
36
37        // Keep track of seen nodes to prevent revisiting
38        unordered_set<TreeNode*> seen;
39
40        // BFS to find the closest leaf
41        while (!toVisit.empty()) {
42            TreeNode* currentNode = toVisit.front();
43            toVisit.pop();
44            seen.insert(currentNode);
45
46            // If current node is a leaf, return its value
47            if (currentNode && !currentNode->left && !currentNode->right) {
48                return currentNode->val;
49            }
50
51            // Enqueue all adjacent nodes
52            for (TreeNode* neighbor : graph[currentNode]) {
53                if (neighbor && !seen.count(neighbor)) {
54                    toVisit.push(neighbor);
55                }
56            }
57        }
58        return 0;
59    }
60
61    // Helper function to perform DFS on tree to build the graph
62    void buildGraph(TreeNode* node, TreeNode* parent) {
63        if (!node) return;
64
65        // Connect the current node with its parent
66        if (parent) {
67            graph[node].push_back(parent);
68            graph[parent].push_back(node);
69        }
70
71        // Continue DFS traversal
72        buildGraph(node->left, node);
73        buildGraph(node->right, node);
74    }
75};
76

Typescript Solution

1// TypeScript typically uses interfaces for defining custom types such as tree nodes.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8// A map to represent the adjacency list of the graph.
9const graph: Map<TreeNode, TreeNode[]> = new Map();
10
11// Convert given binary tree node and its parent into a graph representation.
12function buildGraph(node: TreeNode | null, parent: TreeNode | null): void {
13  if (node === null) return;
14
15  if (!graph.has(node)) {
16    graph.set(node, []);
17  }
18
19  // Connect the current node with its parent.
20  if (parent) {
21    graph.get(node)!.push(parent);
22    if (!graph.has(parent)) {
23      graph.set(parent, []);
24    }
25    graph.get(parent)!.push(node);
26  }
27
28  // Recursive DFS traversal to the left and right child.
29  buildGraph(node.left, node);
30  buildGraph(node.right, node);
31}
32
33// Function to find the closest leaf to a given value 'k' in the binary tree.
34function findClosestLeaf(root: TreeNode, k: number): number {
35  // Convert tree to graph.
36  buildGraph(root, null);
37
38  // Queue to hold nodes to visit during BFS.
39  const toVisit: Queue<TreeNode> = new Queue<TreeNode>();
40
41  // Initialize queue with the node of value 'k'.
42  graph.forEach((_, node) => {
43    if (node.val === k) {
44      toVisit.enqueue(node);
45    }
46  });
47
48  // Set to keep track of visited nodes.
49  const seen: Set<TreeNode> = new Set();
50
51  // BFS to find the closest leaf.
52  while (!toVisit.isEmpty()) {
53    const currentNode = toVisit.dequeue();
54
55    // If reached a leaf, return its value.
56    if (currentNode && !currentNode.left && !currentNode.right) {
57      return currentNode.val;
58    }
59
60    // Mark the current node as seen.
61    seen.add(currentNode);
62
63    // Enqueue all unvisited adjacent nodes.
64    const neighbors = graph.get(currentNode) || [];
65    for (const neighbor of neighbors) {
66      if (!seen.has(neighbor)) {
67        toVisit.enqueue(neighbor);
68      }
69    }
70  }
71
72  // If no leaf is found (edge case), return 0.
73  return 0;
74}
75
76// Simple Queue implementation for TypeScript since there is no native Queue.
77class Queue<T> {
78  private storage: T[] = [];
79
80  enqueue(item: T): void {
81    this.storage.push(item);
82  }
83
84  dequeue(): T | undefined {
85    return this.storage.shift();
86  }
87
88  isEmpty(): boolean {
89    return this.storage.length === 0;
90  }
91}
92
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The time complexity of the code is O(N) where N is the number of nodes in the binary tree. This is because the dfs function traverses each node exactly once to create a graph representation (g) and each edge twice (once for each direction between parent and child). The BFS loop then goes through the nodes in the graph, but each node and edge is considered only once, meaning that it can also be bounded by O(N) in the worst case when we have to visit every node once.

The space complexity is also O(N) because we store every node and its connections in the graph g, which in the worst case could have 2(N - 1) edges (for a binary tree, each parent node could have two children), closely approximating O(N) storage. There is also a seen set tracking visited nodes and a queue q for BFS, both of which could hold at most N elements in the worst-case scenario involving every node in the tree.

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


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫