Medium · Postorder Heights
Understand → Visualise → Practice.
Return the maximum number of edges on any path between two nodes in a heap-indexed binary tree.
Every path has a highest node where it bends. Through node v it uses height(left) + height(right) edges, so compute heights bottom-up and track the best sum.
Height = number of nodes on the longest downward path; an empty child has height 0.
left + right is the number of edges on the longest path bending at this node.
Update the best diameter, and return 1 + max(left, right) to the parent.
O(n) time and O(h) recursion space.
The longest path need not pass through the root.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.