Closest leaf in a binary tree

Tree Depth-First Search Breadth-First Search Binary Tree

47.4% acceptance

Mar 31, 2026

890

189

Given the root of a binary tree where every node has a unique value and a target integer k, return the value of the nearest leaf node to the target k in the tree. Nearest to a leaf means the least number of edges traveled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::{HashMap, VecDeque};
impl Solution {
  pub fn find_closest_leaf(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
    // Build adjacency list (undirected graph) from the tree
    let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
    let mut leaves = Vec::new();
    
    fn build(node: &Option<Rc<RefCell<TreeNode>>>, graph: &mut HashMap<i32, Vec<i32>>, leaves: &mut Vec<i32>) {
      if let Some(n) = node {
        let n = n.borrow();
        let is_leaf = n.left.is_none() && n.right.is_none();
        if is_leaf { leaves.push(n.val); }
        graph.entry(n.val).or_default();
        if let Some(ref left) = n.left {
          let lv = left.borrow().val;
          graph.entry(n.val).or_default().push(lv);
          graph.entry(lv).or_default().push(n.val);
          build(&n.left, graph, leaves);
        }
        if let Some(ref right) = n.right {
          let rv = right.borrow().val;
          graph.entry(n.val).or_default().push(rv);
          graph.entry(rv).or_default().push(n.val);
          build(&n.right, graph, leaves);
        }
      }
    }
    
    build(&root, &mut graph, &mut leaves);
    
    // BFS from k to find nearest leaf
    let leaves_set: std::collections::HashSet<i32> = leaves.into_iter().collect();
    let mut visited = std::collections::HashSet::new();
    let mut queue = VecDeque::new();
    queue.push_back(k);
    visited.insert(k);
    
    while let Some(node) = queue.pop_front() {
      if leaves_set.contains(&node) { return node; }
      if let Some(neighbors) = graph.get(&node) {
        for &nb in neighbors {
          if visited.insert(nb) {
            queue.push_back(nb);
          }
        }
      }
    }
    -1 // unreachable
  }
}