543. Diameter of Binary Tree

This question asks us to find the diameter of a binary tree, which is the longest path between any two nodes in a tree.

If we calculate the path between two nodes in a tree by fixing each node, this would be $O(n^2)$ time. We thus want to calculate the maximum diameter for each node and apply it recursively to the root node, which will find the maximum diameter for the entire tree.

We define a traversal function which DFSes through and returns the height and diameter for each node in the tree.

• The height is 1 + the maximum of the left or right height.
• The diameter is the max of the left_height + right_height (the diameter through this node) or the left diameter or the right diameter.

We then return the max height and max diameter for each node.

class Solution:
    def diameterOfBinaryTree(self, root):
        def traverse(node):
            if not node:
                return 0, 0
            left_height, left_diameter = traverse(node.left)
            right_height, right_diameter = traverse(node.right)
            height = 1 + max(left_height, right_height)
            diameter = max(left_diameter, right_diameter, left_height + right_height)
            return height, diameter
        
        return traverse(root)[1]