Teaching Kids Programming – Breadth First Search Algorithm to Find Bottom Left Tree Value

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.

# 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

The 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) —