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

from collections import deque, defaultdict

class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
        # Step 1: Build graph (undirected) and find the target node
        graph = defaultdict(list)
        target = None

        def dfs(node, parent):
            nonlocal target
            if not node:
                return
            if node.val == k:
                target = node
            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)

        # Step 2: BFS from target node to find the closest leaf
        queue = deque()
        queue.append(target)
        visited = set()
        visited.add(target)
        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)
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>

class Solution {
public:
    int findClosestLeaf(TreeNode* root, int k) {
        std::unordered_map<TreeNode*, std::vector<TreeNode*>> graph;
        TreeNode* target = nullptr;

        // DFS to build undirected graph and find target node
        std::function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* node, TreeNode* parent) {
            if (!node) return;
            if (node->val == k) target = node;
            if (parent) {
                graph[node].push_back(parent);
                graph[parent].push_back(node);
            }
            if (node->left) dfs(node->left, node);
            if (node->right) dfs(node->right, node);
        };

        dfs(root, nullptr);

        // BFS from target
        std::queue<TreeNode*> q;
        std::unordered_set<TreeNode*> visited;
        q.push(target);
        visited.insert(target);

        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            if (!node->left && !node->right) {
                return node->val;
            }
            for (TreeNode* neighbor : graph[node]) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
        return -1; // Should not reach here based on problem constraints
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
        TreeNode[] target = new TreeNode[1];

        // DFS to build graph and find target
        buildGraph(root, null, k, graph, target);

        // BFS from target
        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        queue.offer(target[0]);
        visited.add(target[0]);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) {
                return node.val;
            }
            for (TreeNode neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return -1;
    }

    private void buildGraph(TreeNode node, TreeNode parent, int k, Map<TreeNode, List<TreeNode>> graph, TreeNode[] target) {
        if (node == null) return;
        if (node.val == k) target[0] = node;
        if (parent != null) {
            graph.computeIfAbsent(node, x -> new ArrayList<>()).add(parent);
            graph.computeIfAbsent(parent, x -> new ArrayList<>()).add(node);
        }
        buildGraph(node.left, node, k, graph, target);
        buildGraph(node.right, node, k, graph, target);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var findClosestLeaf = function(root, k) {
    const graph = new Map();
    let target = null;

    function dfs(node, parent) {
        if (!node) return;
        if (node.val === k) target = node;
        if (parent) {
            if (!graph.has(node)) graph.set(node, []);
            if (!graph.has(parent)) graph.set(parent, []);
            graph.get(node).push(parent);
            graph.get(parent).push(node);
        }
        if (node.left) dfs(node.left, node);
        if (node.right) dfs(node.right, node);
    }

    dfs(root, null);

    // BFS from target
    const queue = [target];
    const visited = new Set([target]);
    while (queue.length) {
        const node = queue.shift();
        if (!node.left && !node.right) {
            return node.val;
        }
        for (const neighbor of (graph.get(node) || [])) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return -1;
};