Lowest common ancestor of deepest leaves

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

79.4% acceptance

Feb 27, 2026

2660

949

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves. Recall that: The node of a binary tree is a leaf if and only if it has no children The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1. The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn lca_deepest_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    Self::dfs(&root).0
  }

  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>) -> (Option<Rc<RefCell<TreeNode>>>, i32) {
    match node {
      None => (None, 0),
      Some(n) => {
        let left = n.borrow().left.clone();
        let right = n.borrow().right.clone();
        let (ll, ld) = Self::dfs(&left);
        let (rl, rd) = Self::dfs(&right);
        if ld > rd { (ll, ld + 1) }
        else if rd > ld { (rl, rd + 1) }
        else { (Some(n.clone()), ld + 1) }
      }
    }
  }
}