Problem statement

https://leetcode.com/problems/diameter-of-binary-tree/

Solution

Use auxiliary dfs function, which for each node return the longest left and the longest right paths. Also update the global self.diam, where we evaluate left + right.

Complexity

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

Code

class Solution:
    def diameterOfBinaryTree(self, root):
        self.diam = 0
        def dfs(root):
            if not root: return (0, 0)
            left = max(dfs(root.left))
            right = max(dfs(root.right))
            self.diam = max(self.diam, left + right)
            return (left + 1, right + 1)
        
        dfs(root)
        return self.diam