BinarySearch 0064 Leftmost Deepest Tree Node

Problem statement

https://binarysearch.com/problems/Leftmost-Deepest-Tree-Node/

Solution

Traverse tree once and find the deepest value. Then traverse once again and find all deepest nodes. Then take the first one.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        def dfs1(node):
            if not node: return 0
            return max(dfs1(node.left), dfs1(node.right)) + 1
        
        depth = dfs1(root)
        self.ans = []
        
        def dfs2(node, d):
            if not node: return
            if d == depth: self.ans += [node.val]
            dfs2(node.left, d+1)
            dfs2(node.right, d+1)
            
        dfs2(root, 1)
        return self.ans[0]