Compute binary-tree diameter via return-only DFS
Overview
This question evaluates algorithmic problem-solving with binary trees, focusing on tree traversal techniques, recursion versus iterative implementations, and analysis of time and space complexity including worst-case input shapes such as skewed trees.
Given the root of a binary tree, compute its diameter defined as the number of edges on the longest path between any two nodes. Implement a DFS that returns a tuple to its caller: (height_of_subtree, best_diameter_in_subtree). Combine children’s return values at each node to update the best diameter without using any external list, array, or global variable. Requirements: O(n) time, O(h) auxiliary space where h is the tree height. Edge cases: empty tree (diameter = 0), single node (diameter = 0), completely skewed tree. Then answer: (1) Why does accumulating traversal state in a list during DFS inflate space from O(h) to O(n), and under what input shapes does it hurt most? (2) Provide an iterative postorder version using an explicit stack that still achieves O(h) auxiliary space. (3) State and justify the time and space complexities for both versions.