Closest Leaf in a Binary Tree

medium tree bfs graph

Problem

Given the root of a binary tree where every node value is unique, and a target value k, return the value of the leaf node nearest to the node with value k.

Inputroot=[1,3,2], k=1

Output3

Either leaf (3 or 2) is distance 1 from node 1; BFS visits the left child first, so it returns 3.

input

def findClosestLeaf(root, k):
    from collections import defaultdict, deque
    graph = defaultdict(list)
    target = [None]
    def build(node, parent):
        if not node: return
        if node.val == k: target[0] = node
        if parent:
            graph[node].append(parent); graph[parent].append(node)
        build(node.left, node); build(node.right, node)
    build(root, None)
    q = deque([target[0]])
    seen = {target[0]}
    while q:
        node = q.popleft()
        if not node.left and not node.right: return node.val
        for nb in graph[node]:
            if nb not in seen: seen.add(nb); q.append(nb)

function findClosestLeaf(root, k) {
  const graph = new Map(); let target = null;
  function build(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);
    }
    build(node.left, node); build(node.right, node);
  }
  build(root, null);
  const q = [target]; const seen = new Set([target]);
  while (q.length) {
    const node = q.shift();
    if (!node.left && !node.right) return node.val;
    for (const nb of (graph.get(node) || []))
      if (!seen.has(nb)) { seen.add(nb); q.push(nb); }
  }
}

class Solution {
  TreeNode target; Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
  public int findClosestLeaf(TreeNode root, int k) {
    build(root, null, k);
    Deque<TreeNode> q = new ArrayDeque<>(); Set<TreeNode> seen = new HashSet<>();
    q.offer(target); seen.add(target);
    while (!q.isEmpty()) {
      TreeNode n = q.poll();
      if (n.left == null && n.right == null) return n.val;
      for (TreeNode nb : graph.getOrDefault(n, new ArrayList<>()))
        if (seen.add(nb)) q.offer(nb);
    }
    return -1;
  }
  void build(TreeNode node, TreeNode parent, int k) {
    if (node == null) return;
    if (node.val == k) target = node;
    if (parent != null) {
      graph.computeIfAbsent(node, x -> new ArrayList<>()).add(parent);
      graph.computeIfAbsent(parent, x -> new ArrayList<>()).add(node);
    }
    build(node.left, node, k); build(node.right, node, k);
  }
}

class Solution {
  TreeNode* target = nullptr;
  unordered_map<TreeNode*, vector<TreeNode*>> graph;
public:
  int findClosestLeaf(TreeNode* root, int k) {
    build(root, nullptr, k);
    queue<TreeNode*> q; unordered_set<TreeNode*> seen;
    q.push(target); seen.insert(target);
    while (!q.empty()) {
      TreeNode* n = q.front(); q.pop();
      if (!n->left && !n->right) return n->val;
      for (auto nb : graph[n]) if (!seen.count(nb)) { seen.insert(nb); q.push(nb); }
    }
    return -1;
  }
  void build(TreeNode* node, TreeNode* parent, int k) {
    if (!node) return;
    if (node->val == k) target = node;
    if (parent) { graph[node].push_back(parent); graph[parent].push_back(node); }
    build(node->left, node, k); build(node->right, node, k);
  }
};

Explanation

We need the nearest leaf to a given node k, where "near" can mean going up toward the parent as well as down toward children. A plain tree only lets you go downward, so the key idea is to turn the tree into an undirected graph first.

In the build step we walk the tree and, for every parent-child pair, add an edge in both directions (graph[node].append(parent) and graph[parent].append(node)). Now from any node we can step to its children or its parent. We also remember the node whose value equals k as the target.

Then we run a breadth-first search (BFS) starting from that target. BFS explores everything one step away, then two steps away, and so on, so the first leaf it reaches is guaranteed to be the closest. We use a seen set so we never revisit a node.

Example: tree [1, 3, 2], k = 1. Node 1 is the root with leaves 3 and 2, each one step away. BFS visits neighbours in order and reaches leaf 3 first, so it returns 3.

The graph conversion plus BFS gives us shortest-distance behaviour in any direction, which is exactly what "closest leaf" needs.

Time: O(n) Space: O(n)