# Find Bottom Left Tree Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-bottom-left-tree-value)
Canonical: https://scaleengineer.com/dsa/problems/find-bottom-left-tree-value
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
Given the `root` of a binary tree, return the leftmost value in the last row of the tree.

**Example 1:**

![](https://assets.glich.co/dsa/find-bottom-left-tree-value/image0.jpg) 

**Input:** root = [2,1,3]
**Output:** 1

**Example 2:**

![](https://assets.glich.co/dsa/find-bottom-left-tree-value/image1.jpg) 

**Input:** root = [1,2,3,4,null,5,6,null,null,7]
**Output:** 7

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `-231 <= Node.val <= 231 - 1`

# Approaches
## Depth-First Search (Recursive)
This approach utilizes a recursive Depth-First Search (DFS) to traverse the tree. By keeping track of the traversal depth, we can identify the leftmost node at the deepest level encountered so far. The key is to traverse the left subtree before the right subtree.
**Time:** O(N), where N is the number of nodes in the tree. We visit each node exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be equal to N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** Can be more space-efficient than BFS for wide, shallow trees (e.g., complete binary trees where H = log N).; The recursive implementation is often concise and elegant.
**Cons:** May cause a stack overflow for extremely deep trees due to deep recursion.; In the worst-case (a skewed tree), the space complexity becomes O(N), which is no better than BFS.
### Explanation
The core idea is to traverse the tree while passing down the current level (or depth). We maintain two global or member variables: `maxLevel` to store the maximum depth reached, and `bottomLeftValue` to store the value of the leftmost node at that depth.\n\nWe define a helper function, `dfs(node, level)`. The traversal order is crucial: we must visit the left subtree before the right one. This ensures that when we first encounter a new, deeper level, the node we are at is guaranteed to be the leftmost one for that level.\n\nInside the recursive function, we first check if the current `level` is greater than `maxLevel`. If it is, we've found a new deepest level. We update `maxLevel` to the current `level` and set `bottomLeftValue` to the current node's value. Then, we proceed with the recursive calls for the left and right children.\n\n```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int maxLevel = -1;
    private int bottomLeftValue = 0;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return bottomLeftValue;
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }

        // If this is the first time we visit this level, it must be the leftmost node.
        if (level > maxLevel) {
            maxLevel = level;
            bottomLeftValue = node.val;
        }

        // Traverse left first to ensure we see the leftmost node first at any level.
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}
```
### Algorithm
- Initialize `maxLevel = -1` and `bottomLeftValue` with a default value.
- Create a recursive helper function `dfs(node, level)`.
- Start the traversal by calling `dfs(root, 0)`.
- In `dfs(node, level)`:
    - If `node` is null, return.
    - If the current `level` is greater than `maxLevel`, update `maxLevel = level` and `bottomLeftValue = node.val`.
    - Recursively call `dfs(node.left, level + 1)`.
    - Recursively call `dfs(node.right, level + 1)`.
- After the initial call completes, return `bottomLeftValue`.

## Breadth-First Search (Level Order Traversal)
This approach uses Breadth-First Search (BFS), which naturally explores the tree level by level. By processing all nodes at a given level before moving to the next, we can easily identify the first (leftmost) node of the final level.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the tree. This space is for the queue. In the worst case of a complete binary tree, the last level can have up to N/2 nodes, making the space complexity O(N).
**Pros:** Very intuitive and a natural fit for problems involving tree levels.; More space-efficient than DFS for deep, narrow trees (e.g., skewed trees).; The right-to-left variant provides a particularly clean and simple implementation.
**Cons:** Can consume a large amount of memory for very wide trees, with a worst-case space complexity of O(N).
### Explanation
We use a queue to implement BFS. We start by adding the root to the queue. The algorithm proceeds in a loop as long as the queue is not empty.\n\nIn each iteration of the main loop, we process an entire level. We first determine the number of nodes at the current level (`levelSize`). Then, we loop `levelSize` times, dequeuing one node at a time. The very first node we dequeue in this inner loop (`i == 0`) is the leftmost node of the current level. We store its value in our result variable. As we traverse deeper, this variable gets updated, and its final value will be from the last level.\n\nFor each dequeued node, we enqueue its left and right children, preparing them for the next level's processing.\n\n```java
// Standard Left-to-Right BFS
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int bottomLeftValue = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                if (i == 0) {
                    bottomLeftValue = currentNode.val;
                }
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
        }
        return bottomLeftValue;
    }
}
```

A more elegant variation is to perform a right-to-left BFS. By enqueuing the right child before the left child, the last node we visit at any level is the leftmost one. This means the very last node processed in the entire traversal is our answer, simplifying the code.\n\n```java
// Right-to-Left BFS
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode currentNode = null;

        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }
        }
        return currentNode.val;
    }
}
```
### Algorithm
- Initialize a queue and add the `root` node.
- Initialize a variable `bottomLeftValue`.
- Loop while the queue is not empty:
    - Determine the number of nodes on the current level, `levelSize`.
    - Loop `levelSize` times:
        - Dequeue a `node`.
        - If this is the first node of the level, update `bottomLeftValue = node.val`.
        - Enqueue the node's left child if it exists.
        - Enqueue the node's right child if it exists.
- After the loops complete, return `bottomLeftValue`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int findBottomLeftValue ( TreeNode root ) { Queue < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); int ans = 0 ; while (! q . isEmpty ()) { ans = q . peek (). val ; for ( int i = q . size (); i > 0 ; -- i ) { TreeNode node = q . poll (); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } return ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int findBottomLeftValue ( TreeNode * root ) { queue < TreeNode *> q { { root } }; int ans = 0 ; while ( ! q . empty ()) { ans = q . front () -> val ; for ( int i = q . size (); i ; -- i ) { TreeNode * node = q . front (); q . pop (); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } } return ans ; } };
```

### Python

```python
# 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 class Solution : def findBottomLeftValue ( self , root : Optional [ TreeNode ]) -> int : q = deque ([ root ]) ans = 0 while q : ans = q [ 0 ]. val for _ in range ( len ( q )): node = q . popleft () if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) return ans
```