Find Bottom Left Tree Value

Problem Id: 513 Difficulty: Medium Tag: Tree Tag: Depth-first Search Tag: Breadth-first Search


Intuition

This problem could be solved by DFS with depth as an additional variable, or using BFS and mark the depth of each node.

In this artical, we would use DFS.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = -1
        self.leftmost = None
        self._dfs(root, 0)
        return self.leftmost

    def _dfs(self, node, depth):
        if node is None:
            return
        self._dfs(node.left, depth + 1)
        self._dfs(node.right, depth + 1)

        if depth > self.max_depth:
            self.max_depth = depth
            self.leftmost = node.val