LeetCode Entry

865. Smallest Subtree with all the Deepest Nodes

09.01.2026 medium 2026 kotlin rust

Lowest common ancestor of the deepest nodes

865. Smallest Subtree with all the Deepest Nodes medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1232

Problem TLDR

Lowest common ancestor of the deepest nodes #medium

Intuition

Do a DFS. One way: propagate depth down, compare on the way up. Second way: return both depth & result on the way up.

Approach

• how to use uniqness?

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(logn)\)

Code

// 1ms
    fun subtreeWithAllDeepest(r: TreeNode?): TreeNode? {
        fun dfs(n: TreeNode?): Pair<Int, TreeNode?> = n?.run {
            val (l, a) = dfs(left); val (r, b) = dfs(right)
            (1 + max(l, r)) to if (l > r) a else if (l < r) b else n
        } ?: 0 to null
        return dfs(r).second
    }

// 0ms
    pub fn subtree_with_all_deepest(r: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(ro: &Option<Rc<RefCell<TreeNode>>>, d: i32, max: &mut i32, res: &mut Option<Rc<RefCell<TreeNode>>>) -> i32 {
            let Some(n) = ro else { return d }; let n = n.borrow();
            let (l,r) = (dfs(&n.left, d+1, max, res), dfs(&n.right, d+1, max, res));  *max = l.max(r).max(*max);
            if l == *max && r == *max { *res = ro.clone() }; l.max(r)
        }
        let (mut max, mut res) = (0, None); dfs(&r, 0, &mut max, &mut res); res
    }