LeetCode #513 Find Bottom Left Tree Value

Posted on | Post modified | In , , , , , , , , ,

Problem

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

Examples

1
2
3
4
5
6
7
8
Input:

    2
   / \
  1   3

Output:
1
1
2
3
4
5
6
7
8
9
10
11
12
Input:

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

Output:
7

What If?

  • Input is an empty tree?

Solution1

Method: Breadth-first Search

Time Complexity: O(n)

Space Complexity: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        level = [root]
        res = root.val
        
        while level:
            new_level = []
            res = level[0].val
            
            for node in level:
                if node.left:
                    new_level.append(node.left)
                if node.right:
                    new_level.append(node.right)
            level = new_level
        
        return res

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        queue = collections.deque([(root, 0)])
        res = root.val
        depth_level = 0
        
        while queue:
            node, level = queue.popleft()
            if node:
                if level > depth_level:
                    res = node.val
                    depth_level = level
                queue.append((node.left, level + 1))
                queue.append((node.right, level + 1))
            
        return res

Solution2

Method: Depth-first Search

Time Complexity: O(n)

Space Complexity: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        stack = [(root, 0)]
        res = root.val
        depth_level = 0
        
        while stack:
            node, level = stack.pop()
            if level > depth_level:
                res = node.val
                depth_level = level
            if node.right:
                stack.append((node.right, level + 1))
            if node.left:
                stack.append((node.left, level + 1))
            
        return res