Given the root of a binary tree, return the leftmost value in the last row of the tree.
GoLang: Breadth First Search to Find Bottom Left Binary Tree Value
In GoLang, we make a list and use it as a queue. In Breadth First Search Algorithm, we explore the nodes level by level, and before visiting each nodes on the next level, we save the first node which will the the bottom left tree value when BFS exists.
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 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findBottomLeftValue(root *TreeNode) int { if root == nil { return 0 } var ans int var q = make([]*TreeNode, 0) q = append(q, root) for len(q) > 0 { var sz = len(q) ans = q[0].Val for i := 0; i < sz; i ++ { if q[i].Left != nil { q = append(q, q[i].Left) } if q[i].Right != nil { q = append(q, q[i].Right) } } q = q[sz:] } return ans } |
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) int {
if root == nil {
return 0
}
var ans int
var q = make([]*TreeNode, 0)
q = append(q, root)
for len(q) > 0 {
var sz = len(q)
ans = q[0].Val
for i := 0; i < sz; i ++ {
if q[i].Left != nil {
q = append(q, q[i].Left)
}
if q[i].Right != nil {
q = append(q, q[i].Right)
}
}
q = q[sz:]
}
return ans
}The time and space complexity is both O(N) where N is the number of the nodes in the given binary tree. The usage of a queue to implement the BFS makes O(N) space complexity.
GoLang: Depth First Search to Find Bottom Left Binary Tree Value
We can also use the Depth First Search algorithm to traverse the binary tree. We also need to make a map that stores the first node of each level.
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 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findBottomLeftValue(root *TreeNode) int { var data = make(map[int]*TreeNode) dfs(root, 0, data) var ans int var lvl int = -1 for key, val := range data { if key > lvl { lvl = key ans = val.Val } } return ans } func dfs(root *TreeNode, lvl int, data map[int]*TreeNode) { if root == nil { return } if _, ok := data[lvl]; !ok { data[lvl] = root } dfs(root.Left, lvl + 1, data) dfs(root.Right, lvl + 1, data) } |
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) int {
var data = make(map[int]*TreeNode)
dfs(root, 0, data)
var ans int
var lvl int = -1
for key, val := range data {
if key > lvl {
lvl = key
ans = val.Val
}
}
return ans
}
func dfs(root *TreeNode, lvl int, data map[int]*TreeNode) {
if root == nil {
return
}
if _, ok := data[lvl]; !ok {
data[lvl] = root
}
dfs(root.Left, lvl + 1, data)
dfs(root.Right, lvl + 1, data)
}The Depth First Search algorithm is usually implemented in Recursion. The time and space complexity is O(N) as well.
The DFS takes the node, the current level and the map to store the key-value (level and TreeNode).
Other implementations of finding bottom left node of a binary tree either in BFS or DFS Algorithms:
- Teaching Kids Programming – Breadth First Search Algorithm to Find Bottom Left Tree Value
- GoLang: Find Bottom Left Tree Value via Depth First Search or Breadth First Search Algorithm
- Teaching Kids Programming – Depth First Search Algorithm to Find Bottom Left Tree Value
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Claim the Witness (Super Representative) Voting Rewards on Tron Blockchain using Node Js (Javascript)?
Next Post: Teaching Kids Programming - Depth First Search Algorithm to Find Bottom Left Tree Value