Problem statement

https://leetcode.com/problems/find-bottom-left-tree-value/

Solution

There is also dfs solution, where we traverse and count level of node, also we keep maximum level reached. If we find higher level, we update our candidate for leftmost element.

Complexity

Time complexity is O(n) and space complexity is O(h).

Code

class Solution:
    def findBottomLeftValue(self, root):
        self.found = (-1, -1)
        
        def dfs(node, level):
            if not node: return
            if level > self.found[0]:
                self.found = (level, node.val)
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
            
        dfs(root, 0)
        return self.found[1]

Remark

There is also bfs solution, where we traverse tree layer by layer and when new layer starts, we update the candidate of leftmost element. Time complexity is O(n), space complexity is O(W), where W is width of tree, potentially can be O(n) (or we can traverse first right, and then left node, in this way we just return the last node!)