LeetCode Entry

513. Find Bottom Left Tree Value

28.02.2024 medium 2024 kotlin rust

Leftmost node value of the last level of the Binary Tree.

513. Find Bottom Left Tree Value medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/522

Problem TLDR

Leftmost node value of the last level of the Binary Tree.

Intuition

Just solve this problem for both left and right children, then choose the winner with most depth.

Approach

Code looks nicer when dfs function accepts nullable value.

Complexity

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

  • Space complexity: \(O(log(n))\)

Code


  fun findBottomLeftValue(root: TreeNode?): Int {
    fun dfs(n: TreeNode?): List<Int> = n?.run {
      if (left == null && right == null) listOf(`val`, 1) else {
        val l = dfs(left); val r = dfs(right)
        val m = if (r[1] > l[1]) r else l
        listOf(m[0], m[1] + 1)
    }} ?: listOf(Int.MIN_VALUE, 0)
    return dfs(root)[0]
  }



  pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(n: &Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
      n.as_ref().map_or((i32::MIN, 0), |n| { let n = n.borrow();
        if !n.left.is_some() && !n.right.is_some() { (n.val, 1) } else {
          let (l, r) = (dfs(&n.left), dfs(&n.right));
          let m = if r.1 > l.1 { r } else { l };
          (m.0, m.1 + 1)
      }})}
    dfs(&root).0
  }