Diameter of Binary Tree

The problem description can be found in LeetCode.

Approach

The same considerations made for the Balanced Binary Tree problem apply here.

For this problem, we can simply calculate every possible diameter. In order to do so, it is enough to calculate it for every node of the tree and keep track of the maximum value, which will be our result.

However, in this case I want to show how it possible to return multiple values from the recursive function. An alternative approach would consist of having a global variable to keep track of the maximum diameter.

Solution

from typing import Optional, Tuple


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> Tuple[int, int]:
            if not root:
                return 0, 0

            left_height, left_diameter = dfs(root.left)
            right_height, right_diameter = dfs(root.right)

            diameter = max(
                left_height + right_height,
                left_diameter,
                right_diameter,
            )

            return 1 + max(left_height, right_height), diameter

        _, diameter = dfs(root)
        return diameter

Complexity

• Time: $O(n)$
• Space: $O(h)$

Where $n$ is the number of nodes in the tree and $h$ is its height. If the tree is unbalanced, it is like having a Linked List, hence $h=n$.