Problem statement

https://binarysearch.com/problems/Second-Place/

Solution

Just perform dfs and then choose the second biggest depth.

Complexity

Here we can say it is O(n), because we can have not a lot of unique depths.

Code

class Solution:
    def solve(self, root):
        d = set()
        def dfs(node, dep):
            if not node.left and not node.right: d.add(dep)
            if node.left:  dfs(node.left, dep + 1)
            if node.right: dfs(node.right, dep + 1)

        dfs(root, 0)
        return sorted(d)[-2]