# 04.04.2025 [1123. Lowest Common Ancestor of Deepest Leaves]

Lowest common ancestor of deepest tree nodes #medium #recursion

04.04.2025

1123. Lowest Common Ancestor of Deepest Leaves medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/948

Problem TLDR

Lowest common ancestor of deepest tree nodes #medium #recursion

Intuition

Solve the problem for the left and right subtrees. Update ancestor of both left and right have equal depths.

Approach

• provide examples of several deepest nodes to better understand what is asked

Complexity

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

• Space complexity: $$O(log(n))$$ recursion depth

Code

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

    fun lcaDeepestLeaves(root: TreeNode?): TreeNode? {
        var max = 0; var res = root
        fun d(n: TreeNode?, lvl: Int): Int {
            max = max(lvl, max); n ?: return lvl
            val l = d(n.left, lvl + 1); val r = d(n.right, lvl + 1)
            if (l == max && l == r) res = n
            return max(l, r)
        }
        d(root, 0)
        return res
    }

    pub fn lca_deepest_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        fn d(no: Option<Rc<RefCell<TreeNode>>>) -> (i32, Option<Rc<RefCell<TreeNode>>>) {
            let Some(nrc) = no.clone() else { return (0, no) }; let n = nrc.borrow();
            let (a, l) = d(n.left.clone()); let (b, r) = d(n.right.clone());
            if a == b { (a + 1, no) } else if a > b { (a + 1, l) } else { (b + 1, r) }
        }
        d(root.clone()).1
    }

    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        auto d = [&](this const auto& d, TreeNode* n) -> pair<int, TreeNode*> {
            if (!n) return {0, n}; auto [a, l] = d(n->left); auto [b, r] = d(n->right);
            if (a == b) return {a + 1, n}; if (a > b) return {a + 1, l}; return {b + 1, r};
        };
        return d(root).second;
    }