Leetcode 513. Find Bottom Left Tree Value (Python)

Related Topic

Breadth-First-Search.

Description

Given a binary tree, find the leftmost value in the last row of the tree.

Sample I/O

Example 1

Input:

    2
   / \
  1   3

Output:
1

Example 2

Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

Note

You may assume the tree (i.e., the given root node) is not NULL.

Methodology

Use BFS to traversal until last level. The left most node is the first element of the last level

Code(BFS)

def findBottomLeftValue(self, root: TreeNode) -> int:
        levels = [root]
        ans = 0
        while levels:
            nxt = []
            for node in levels:
                if node.left:
                    nxt.append(node.left)
                if node.right:
                    nxt.append(node.right)
            if not nxt:
                ans = levels[0].val
                break
            levels = nxt
        return ans

BigO

We traversal all elements of the tree once so total time complexity is O(n)