{x}
blog image

Closest Leaf in a Binary Tree

742. Closest Leaf in a Binary Tree

Problem Description

Given a binary tree where each node has a unique value and a target integer k, find the value of the nearest leaf node to the target k. A leaf node is a node with no children. "Nearest" means the minimum number of edges to traverse from the target node to a leaf node.

Solution: DFS + BFS

This solution uses a two-step approach:

  1. Depth-First Search (DFS) to build an adjacency graph: The DFS traversal creates an undirected graph representing the tree's connections. Each node is connected to its parent, left child, and right child. This allows us to easily traverse the tree from any node, regardless of the parent-child relationship.

  2. Breadth-First Search (BFS) to find the closest leaf: Starting from the target node (k), BFS systematically explores the graph level by level. The first leaf node encountered is the closest leaf.

Algorithm

  1. DFS:

    • A recursive dfs function traverses the tree.
    • It adds edges to the graph (g) connecting each node to its parent, left child, and right child. The graph is implemented using a dictionary (Python) or map (Java, C++, Go) where keys are nodes and values are lists of adjacent nodes.
    • We pass the parent node (fa) as an argument to connect each node to its parent.

  2. BFS:

    • Initialize a queue q with the target node (the node with value k).
    • Maintain a vis set to keep track of visited nodes during the BFS traversal. This prevents cycles and ensures efficient search.
    • Start BFS:
      • Dequeue a node from q.
      • If it's a leaf node (no children), return its value.
      • Otherwise, add its unvisited neighbors to q and mark them as visited in vis.

Time and Space Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. Both DFS and BFS traverse the tree at most once.
  • Space Complexity: O(N) to store the adjacency graph g and the vis set. In the worst case (a skewed tree), the queue in BFS can also take O(N) space.

Code Implementation (Python3, Java, C++, Go)

The code implementations below demonstrate the algorithm in different programming languages. They all follow the same core logic. Note that the specific data structures (e.g., defaultdict, HashMap, unordered_map) might differ slightly across languages.

Python3

from collections import defaultdict, deque
 
# ... (TreeNode definition) ...
 
class Solution:
    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        # DFS to build the graph
        g = defaultdict(list)
        def dfs(root, fa):
            if root:
                g[root].append(fa)
                g[fa].append(root)
                dfs(root.left, root)
                dfs(root.right, root)
        dfs(root, None)
 
        # BFS to find the closest leaf
        q = deque([node for node in g if node and node.val == k])
        vis = {node for node in q}  # Use a set for efficient membership checking
        while q:
            node = q.popleft()
            if not node.left and not node.right:  # Leaf node
                return node.val
            for neighbor in g[node]:
                if neighbor not in vis:
                    vis.add(neighbor)
                    q.append(neighbor)

Java

import java.util.*;
 
// ... (TreeNode definition) ...
 
class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, List<TreeNode>> g = new HashMap<>();
        dfs(root, null, g);
 
        Queue<TreeNode> q = new LinkedList<>();
        Set<TreeNode> vis = new HashSet<>();
        for (TreeNode node : g.keySet()) {
            if (node != null && node.val == k) {
                q.offer(node);
                vis.add(node);
                break;
            }
        }
 
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) {
                return node.val;
            }
            for (TreeNode neighbor : g.get(node)) {
                if (!vis.contains(neighbor)) {
                    vis.add(neighbor);
                    q.offer(neighbor);
                }
            }
        }
        return -1; //Should not reach here if k exists.
    }
 
    private void dfs(TreeNode root, TreeNode parent, Map<TreeNode, List<TreeNode>> g) {
        if (root == null) return;
        g.computeIfAbsent(root, k -> new ArrayList<>()).add(parent);
        if(parent != null) g.computeIfAbsent(parent, k -> new ArrayList<>()).add(root);
        dfs(root.left, root, g);
        dfs(root.right, root, g);
    }
}

C++

#include <unordered_map>
#include <vector>
#include <queue>
#include <unordered_set>
 
// ... (TreeNode definition) ...
 
class Solution {
public:
    int findClosestLeaf(TreeNode* root, int k) {
        unordered_map<TreeNode*, vector<TreeNode*>> g;
        dfs(root, nullptr, g);
 
        queue<TreeNode*> q;
        unordered_set<TreeNode*> vis;
        for (auto const& [node, adj] : g) {
            if (node && node->val == k) {
                q.push(node);
                vis.insert(node);
                break;
            }
        }
 
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (!node->left && !node->right) {
                return node->val;
            }
            for (TreeNode* neighbor : g[node]) {
                if (vis.find(neighbor) == vis.end()) {
                    vis.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
        return -1; // Should not reach here
    }
 
private:
    void dfs(TreeNode* root, TreeNode* parent, unordered_map<TreeNode*, vector<TreeNode*>>& g) {
        if (!root) return;
        g[root].push_back(parent);
        if (parent) g[parent].push_back(root);
        dfs(root->left, root, g);
        dfs(root->right, root, g);
    }
};

Go

// ... (TreeNode definition) ...
 
func findClosestLeaf(root *TreeNode, k int) int {
	g := make(map[*TreeNode][]*TreeNode)
	var dfs func(*TreeNode, *TreeNode)
	dfs = func(root, parent *TreeNode) {
		if root == nil {
			return
		}
		g[root] = append(g[root], parent)
		if parent != nil {
			g[parent] = append(g[parent], root)
		}
		dfs(root.Left, root)
		dfs(root.Right, root)
	}
	dfs(root, nil)
 
	q := []*TreeNode{}
	vis := make(map[*TreeNode]bool)
	for node := range g {
		if node != nil && node.Val == k {
			q = append(q, node)
			vis[node] = true
			break
		}
	}
 
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		if node.Left == nil && node.Right == nil {
			return node.Val
		}
		for _, neighbor := range g[node] {
			if !vis[neighbor] {
				vis[neighbor] = true
				q = append(q, neighbor)
			}
		}
	}
	return -1 //Should not reach here
}

These code examples implement the DFS + BFS approach efficiently to solve the problem. Remember to handle edge cases (e.g., empty tree, target node not found). The choice of language primarily affects the syntax and specific data structures used, but the core algorithmic steps remain consistent.