TreeNode(val, left=None, right=None) is in the starter. Keep it.
Implement diameter_of_binary_tree(root) -> int: the number of edges on the longest path between any two nodes of the tree. The path doesn't have to pass through the root. An empty tree or a single node has diameter 0.
# 1
# / \
# 2 3
# / \
# 4 5
diameter_of_binary_tree(root) # 3 (4 -> 2 -> 1 -> 3, or 5 -> 2 -> 1 -> 3)
The tree has up to 100,000 nodes and can be lopsided (up to a few thousand levels deep; the Python tests raise the recursion limit for you). Aim for O(n): recomputing heights from scratch at every node is too slow.
Show hint
The longest path that bends at a node goes down into its left and right subtrees, so its length depends on their heights. A single traversal can return each subtree's height to its parent while keeping track of the best bend seen so far.