Description

The diameter of a Binary Tree is the longest path (in terms of edges) between any two nodes in the tree.

Runtime

O(log(n))

Visualization

Pseudocode

Get the max depth of the right node, and the left node
Add them together. (this is their diameter)
Check if it is bigger then the current largest diameter.
If it is update the largest diameter

Code

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        self.max_depth(root)
        return self.diameter

    def max_depth(self, node):
        if node == None:
            return -1

        left = self.max_depth(node.left) + 1
        right = self.max_depth(node.right) + 1

        diameter = left + right

        if diameter > self.diameter:
            self.diameter = diameter

        return max(left, right)