The diameter is the number of edges on the longest path between any two nodes. The path does not have to pass through the root.
DSA Animator › DSA Revision › Tree › Diameter of Binary Tree
Remember: return height, but record the diameter on the side. Left height plus right height is the path that bends at this node. The video solves Diameter of Binary Tree (LeetCode 543, Easy) with the DFS Height pattern from the Tree topic, and you can replay every step in the interactive Diameter of Binary Tree animation.
The diameter is the number of edges on the longest path between any two nodes. The path does not have to pass through the root.
For the tree 1, with children 2 and 3, where 2 has children 4 and 5, the diameter is 3. One longest path is 4, 2, 1, 3, which has three edges.
For every node, you could compute the heights of its two subtrees separately. Recomputing heights again and again makes that O of n squared. We can get every height and every candidate in a single pass.
Write a function that returns the height of a node, counted in nodes. For a node, ask for the left height and the right height. The longest path that bends at this node uses left plus right edges. Update a global best with left plus right. Then return 1 plus the larger of the two heights to the parent.
Leaves 4 and 5 return height 1, and the path through them alone has 0 edges. At node 2, left is 1 and right is 1, so the path through 2 has 2 edges. The best so far is 2, and node 2 returns height 2. Leaf 3 returns height 1. At the root, left is 2 and right is 1, so the path through 1 has 3 edges. The best becomes 3, and the answer is 3.
In code, keep a field called best. The height function returns 0 for null. Otherwise it computes left and right heights, sets best to the larger of best and left plus right. Then it returns 1 plus the larger height. One pass over the tree, so it's O of n time.
Remember: return height, but record the diameter on the side. Left height plus right height is the path that bends at this node.