keetcoder

# 513. Find Bottom Left Tree Value

LeetCode Problem Link (opens new window)

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

513. Find Bottom Left Tree Value

Example 2:

513. Find Bottom Left Tree Value

# Thought Process

The goal is to find the leftmost value of the last row in the tree. Using level-order traversal (breadth-first search) would be straightforward, whereas recursion might be a bit more challenging.

Let's first discuss the recursive approach.

# Recursive

At first glance, using recursion might suggest simply traversing left until reaching the end. However, this isn't so straightforward — just going left doesn't guarantee you're at the last row.

Let's analyze the problem: We need to find both the last row and the leftmost value.

To solve this recursively, the key is recognizing the leaf node with the greatest depth, which will belong to the last row.

For further understanding of tree depth and height, refer to 0110.Balanced Binary Tree (opens new window).

The solution involves finding the deepest leaf node, then capturing its leftmost occurrence.

Steps in Recursion:

  1. Define the function parameters and return type

The function will need parameters for the root of the tree and an integer to track the maximum depth. No need for a return type, so it will be void.

The solution involves two global variables: maxDepth to track the greatest depth, and result to store the value of the leftmost node at max depth.

The code is as follows:

int maxDepth = INT_MIN;   // Global variable for maximum depth
int result;       // Global variable for leftmost node value at max depth
void traversal(TreeNode* root, int depth)
1
2
3
  1. Define the base case

When reaching a leaf node, it's time to check for a new maximum depth at the node. This is when you update the leftmost value if it's the deepest leaf node encountered.

The code is as follows:

if (root->left == NULL && root->right == NULL) {
    if (depth > maxDepth) {
        maxDepth = depth;           // Update maximum depth
        result = root->val;   // Record node's value at max depth 
    }
    return;
}
1
2
3
4
5
6
7
  1. Establishing the recursive logic

While finding maximum depth, recursive operations include backtracking:

                    // Process node
if (root->left) {   // Traverse left
    depth++; // Increment depth
    traversal(root->left, depth);
    depth--; // Backtrack, decrement depth
}
if (root->right) { // Traverse right
    depth++; // Increment depth
    traversal(root->right, depth);
    depth--; // Backtrack, decrement depth
}
return;
1
2
3
4
5
6
7
8
9
10
11
12

Full code:

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // Backtracking
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // Backtracking
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Backtracking could be simplified. Simplified code:

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            traversal(root->left, depth + 1); // Hidden backtracking
        }
        if (root->right) {
            traversal(root->right, depth + 1); // Hidden backtracking
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

If the simplified backtracking part is unclear, refer to 0257.Binary Tree Paths (opens new window).

# Iterative Approach

Level-order traversal (breadth-first search) is ideal here and more intuitive than recursion!

Simply capture the first value of the last level traversed.

For those unfamiliar with level-order traversal, refer to 0102.Binary Tree Level Order Traversal (opens new window) which provides a detailed explanation and template.

Here's the code:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // Record first element of last row
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Summary

This problem touches on several topics:

These covered points equip you with flexible algorithmic application skills far beyond just this problem.

# Code in Other Languages

# Java

// Recursive
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Iterative
class Solution {

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == 0) {
                    res = poll.val;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Python

(Version 1) Recursive + Backtracking

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = float('-inf')
        self.result = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if node.left:
            depth += 1
            self.traversal(node.left, depth)
            depth -= 1
        if node.right:
            depth += 1
            self.traversal(node.right, depth)
            depth -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

(Version 2) Recursive + Simplified

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = float('-inf')
        self.result = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if node.left:
            self.traversal(node.left, depth+1)
        if node.right:
            self.traversal(node.right, depth+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(Version 3) Iterative

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def findBottomLeftValue(self, root):
        if root is None:
            return 0
        queue = deque()
        queue.append(root)
        result = 0
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == 0:
                    result = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Go

Recursive:

var depth int   // Global variable for max depth
var res int     // Record final result
func findBottomLeftValue(root *TreeNode) int {
    depth, res = 0, 0   // Initialize
    dfs(root, 1)
    return res
}

func dfs(root *TreeNode, d int) {
    if root == nil {
        return
    }
    // Prioritize left; therefore, if left side has value, same-level right side won't update result
    if root.Left == nil && root.Right == nil && depth < d { 
        depth = d
        res = root.Val
    }
    dfs(root.Left, d+1)   // Hidden backtracking
    dfs(root.Right, d+1)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Iterative:

func findBottomLeftValue(root *TreeNode) int {
    var gradation int
    queue := list.New()
    
    queue.PushBack(root)
    for queue.Len() > 0 {
        length := queue.Len()
        for i := 0; i < length; i++ {
            node := queue.Remove(queue.Front()).(*TreeNode)
            if i == 0 {
                gradation = node.Val
            }
            if node.Left != nil {
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
    }
    return gradation
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# JavaScript

Recursive:

var findBottomLeftValue = function(root) {
    // First consider recursive traversal with pre-order traversal to find the deepest leaf node
    let maxPath = 0, resNode = null;
    // 1. Define the recursive function's parameters
    const dfsTree = function(node, curPath) {
    // 2. Define the recursion termination condition
        if(node.left === null && node.right === null) {
            if(curPath > maxPath) {
                maxPath = curPath;
                resNode = node.val;
            }
        }
        node.left && dfsTree(node.left, curPath+1);
        node.right && dfsTree(node.right, curPath+1);
    }
    dfsTree(root,1);
    return resNode;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Level-order Traversal:

var findBottomLeftValue = function(root) {
    // Consider level-order traversal, record the first node of the last layer
    let queue = [];
    if(root === null) { 
        return null;
    }
    queue.push(root);
    let resNode;
    while(queue.length) {
        let length = queue.length;
        for(let i = 0; i < length; i++) {
            let node = queue.shift();
            if(i === 0) {
                resNode = node.val;
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return resNode;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# TypeScript

Recursive:

function findBottomLeftValue(root: TreeNode | null): number {
    function recur(root: TreeNode, depth: number): void {
        if (root.left === null && root.right === null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                resVal = root.val;
            }
            return;
        }
        if (root.left !== null) recur(root.left, depth + 1);
        if (root.right !== null) recur(root.right, depth + 1);
    }
    let maxDepth: number = 0;
    let resVal: number = 0;
    if (root === null) return resVal;
    recur(root, 1);
    return resVal;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Level-order Traversal:

function findBottomLeftValue(root: TreeNode | null): number {
    let helperQueue: TreeNode[] = [];
    if (root !== null) helperQueue.push(root);
    let resVal: number = 0;
    let tempNode: TreeNode;
    while (helperQueue.length > 0) {
        resVal = helperQueue[0].val;
        for (let i = 0, length = helperQueue.length; i < length; i++) {
            tempNode = helperQueue.shift()!;
            if (tempNode.left !== null) helperQueue.push(tempNode.left);
            if (tempNode.right !== null) helperQueue.push(tempNode.right);
        }
    }
    return resVal;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Swift

Recursive:

var maxLen = -1
var maxLeftValue = 0
func findBottomLeftValue_2(_ root: TreeNode?) -> Int {
    traversal(root, 0)
    return maxLeftValue
}

func traversal(_ root: TreeNode?, _ deep: Int) {
    guard let root = root else {
        return
    }

    if root.left == nil && root.right == nil {
        if deep > maxLen {
            maxLen = deep
            maxLeftValue = root.val
        }
        return
    }
    
    if root.left != nil {
        traversal(root.left, deep + 1)
    }
    
    if root.right != nil {
        traversal(root.right, deep + 1)
    }
    return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Level-order Traversal:

func findBottomLeftValue(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    
    var queue = [root]
    var result = 0
    
    while !queue.isEmpty {
        let size = queue.count
        for i in 0..<size {
            let firstNode = queue.removeFirst()
          
            if i == 0 {
                result = firstNode.val
            }
            
            if let leftNode = firstNode.left {
                queue.append(leftNode)
            }
            
            if let rightNode = firstNode.right {
                queue.append(rightNode)
            }
        }
    }
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Scala

Recursive:

object Solution {
  def findBottomLeftValue(root: TreeNode): Int = {
    var maxLeftValue = 0
    var maxLen = Int.MinValue
    // Recursive method
    def traversal(node: TreeNode, depth: Int): Unit = {
      // Check for leftmost node on a new deepest level
      if (node.left == null && node.right == null && depth > maxLen) {
        maxLen = depth
        maxLeftValue = node.value
      }
      if (node.left != null) traversal(node.left, depth + 1)
      if (node.right != null) traversal(node.right, depth + 1)
    }
    traversal(root, 0)
    maxLeftValue
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Level-order Traversal:

  import scala.collection.mutable

  def findBottomLeftValue(root: TreeNode): Int = {
    val queue = mutable.Queue[TreeNode]()
    queue.enqueue(root)
    var res = 0
    while (!queue.isEmpty) {
      val len = queue.size
      for (i <- 0 until len) {
        val curNode = queue.dequeue()
        if (i == 0) res = curNode.value
        if (curNode.left != null) queue.enqueue(curNode.left)
        if (curNode.right != null) queue.enqueue(curNode.right)
      }
    }
    res
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Rust

Level-order Traversal

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut queue = VecDeque::new();
        let mut res = 0;
        if root.is_some() {
            queue.push_back(root);
        }
        while !queue.is_empty() {
            for i in 0..queue.len() {
                let node = queue.pop_front().unwrap().unwrap();
                if i == 0 {
                    res = node.borrow().val;
                }
                if node.borrow().left.is_some() {
                    queue.push_back(node.borrow().left.clone());
                }
                if node.borrow().right.is_some() {
                    queue.push_back(node.borrow().right.clone());
                }
            }
        }
        res
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Recursive

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = 0;
        let mut max_depth = i32::MIN;
        Self::traversal(root, 0, &mut max_depth, &mut res);
        res
    }
    fn traversal(
        root: Option<Rc<RefCell<TreeNode>>>,
        depth: i32,
        max_depth: &mut i32,
        res: &mut i32,
    ) {
        let node = root.unwrap();
        if node.borrow().left.is_none() && node.borrow().right.is_none() {
            if depth > *max_depth {
                *max_depth = depth;
                *res = node.borrow().val;
            }
            return;
        }
        if node.borrow().left.is_some() {
            Self::traversal(node.borrow().left.clone(), depth + 1, max_depth, res);
        }
        if node.borrow().right.is_some() {
            Self::traversal(node.borrow().right.clone(), depth + 1, max_depth, res);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# C#

//Recursive
int maxDepth = -1;
int res = 0;
public int FindBottomLeftValue(TreeNode root)
{
    Traversal(root, 0);
    return res;
}
public void Traversal(TreeNode root, int depth)
{
    if (root.left == null && root.right == null)
    {
        if (depth > maxDepth)
        {
            maxDepth = depth;
            res = root.val;
        }
        return;
    }
    if (root.left != null)
    {
        Traversal(root.left, depth + 1);
    }
    if (root.right != null)
    {
        Traversal(root.right, depth + 1);
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * @lc app=leetcode id=513 lang=csharp
 * Iterative
 * [513] Find Bottom Left Tree Value
 */

// @lc code=start
public class Solution
{
    public int FindBottomLeftValue(TreeNode root)
    {
        Queue<TreeNode> que = new Queue<TreeNode>();

        if (root != null)
        {
            que.Enqueue(root);
        }
        
        int ans = 0;
        while (que.Count != 0)
        {
           
            int size = que.Count;
            for (var i = 0; i < size; i++)
            {
                var curNode = que.Peek();
                que.Dequeue();
                if(i == 0){
                    ans = curNode.val;
                }
                if (curNode.left != null)
                {
                    que.Enqueue(curNode.left);
                }
                if (curNode.right != null)
                {
                    que.Enqueue(curNode.right);
                }
            }

        }
        return ans;
    }
}
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Last updated:: 9/4/2025, 3:19:38 PM

← 15. Path Sum →

Copyright © 2025 keetcoder