LeetCode Entry

404. Sum of Left Leaves

14.04.2024 easy 2024 kotlin rust

Left-leaf sum in a Binary Tree

404. Sum of Left Leaves easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/571

Problem TLDR

Left-leaf sum in a Binary Tree #easy

Intuition

Do a Depth-First Search and check if left node is a leaf

Approach

Let’s try to reuse the original method’s signature.

• in Rust Rc::clone is a cheap operation

Complexity

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

• Space complexity: \(O(log(n))\), for the recursion stack space

Code

    fun sumOfLeftLeaves(root: TreeNode?): Int = root?.run {
       (left?.takeIf { it.left == null && it.right == null }?.`val` ?:
       sumOfLeftLeaves(left)) + sumOfLeftLeaves(right)
    } ?: 0

    pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        root.as_ref().map_or(0, |n| { let n = n.borrow();
            n.left.as_ref().map_or(0, |left| { let l = left.borrow();
                if l.left.is_none() && l.right.is_none() { l.val }
                else { Self::sum_of_left_leaves(Some(Rc::clone(left))) }
            }) +
            n.right.as_ref().map_or(0, |r| Self::sum_of_left_leaves(Some(Rc::clone(r))))
        })
    }