DSA problem
Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes in the tree, where length is measured in edges. The path does not necessarily pass through the root.
The crucial observation is that the longest path passing through a given node v consists of the longest downward path into v's left subtree, plus the longest downward path into v's right subtree. That sum equals depth(v.left) + depth(v.right) (in edges). The global diameter is simply the maximum of this quantity over every node.
This naturally suggests a single post-order traversal. As the recursion returns from each subtree, it reports back the depth of that subtree (the longest downward path in edges). At every node we use the two reported depths to update a global best, and we return 1 + max(leftDepth, rightDepth) to our parent so it can do the same.
The algorithm visits each node exactly once and performs constant work per node, so it runs in O(n) time and uses O(h) stack space. A common pitfall is to confuse depth (length of the longest downward path, measured in edges) with number of nodes on that path; sticking to "edges only" everywhere keeps the arithmetic clean.
Examples
root = [1,2,3,4,5]3root = [1,2]1root = [1]0Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -100 <= Node.val <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.