Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root of a binary tree, return the leftmost value in the last row of the tree.
Depth First Search Algorithm to Find Bottom Left Tree Value
We can perform a Depth First Search Algorithm in particular the preorder (Node-Left-Right). Everytime we visit a new level, we record the Node in a hash map. The first visited Node will be the left most node of that level.
After Depth First Search, we return the the value of the entry which has the largest key (level).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 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: TreeNode) -> int: if not root: return None data = {} def dfs(root, lvl): nonlocal data if root is None: return if lvl not in data: data[lvl] = root dfs(root.left, lvl + 1) dfs(root.right, lvl + 1) dfs(root, 0) return data[max(data.keys())].val |
# 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: TreeNode) -> int:
if not root:
return None
data = {}
def dfs(root, lvl):
nonlocal data
if root is None:
return
if lvl not in data:
data[lvl] = root
dfs(root.left, lvl + 1)
dfs(root.right, lvl + 1)
dfs(root, 0)
return data[max(data.keys())].valIn order to perform DFS, we need to pass down (and update) the level when we navigate a nodes’ left and right tree.
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) —
GD Star Rating
loading...
476 wordsloading...
Last Post: GoLang: Find Bottom Left Tree Value via Depth First Search or Breadth First Search Algorithm
Next Post: Redistribute Characters to Make All Strings Equal
