Answer: Nutanix OA Question 2024 September | Trees | on-campus

Solution: Diameter of Binary Tree — DFS Height with Global Max Approach We use a Recursive DFS. For every node, the longest path passing through that node is: leftHeight + rightHeight where leftHeight and rightHeight are the heights of its left and right subtrees respectively. We maintain a global maximum across all nodes because the diameter may not pass through the root. Recursively compute the height of each subtree. At each node, update the global diameter with leftHeight + rightHeight. ...