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.
Find Bottom Left Tree Value via Breadth First Search Algorithm
We can use Breadth First Search Algorithm (BFS) to perform a level by level tree traversal. We remember the last left-most value 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 | # 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 q = deque([root]) ans = None while q: sz = len(q) ans = q[0].val for i in range(sz): cur = q.popleft() if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) return ans |
# 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
q = deque([root])
ans = None
while q:
sz = len(q)
ans = q[0].val
for i in range(sz):
cur = q.popleft()
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return ansThe time complexity is O(N) and so is the space complexity where N is the number of the nodes in the given binary 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...
442 wordsloading...
Last Post: Automate Freeze (Stake) Balance on Tron Blockchain using NodeJs with TronWeb/TronGrid
Next Post: How to Claim the Witness (Super Representative) Voting Rewards on Tron Blockchain using Node Js (Javascript)?
