# 2022-06-22

## 513. Find Bottom Left Tree Value

### Description

Given the `root` of a binary tree, return the leftmost value in the last row of the tree.

Example 1:

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

Example 2:

``````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, 10^4]`.

• `-23^1 <= Node.val <= 23^1 - 1`

### Solution

#### Approach #0: BFS

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) (ans int) {
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[i]
if i == 0 {
ans = node.Val
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
queue = queue[size:]
}
return
}``````

#### Approach #1: BFS

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) (ans int) {
queue := []*TreeNode{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node.Right != nil {
queue = append(queue, node.Right)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
ans = node.Val
}
return
}``````

#### Approach #2: DFS

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) (ans int) {
var cur int
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
depth++
dfs(node.Left, depth)
dfs(node.Right, depth)
if depth > cur {
cur = depth
ans = node.Val
}
}
dfs(root, 0)
return
}``````

Last updated