Diameter of Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree. The task is to compute the tree's diameter, defined as the number of edges on the longest path between any two nodes. The path may or may not pass through the root.

Approach 1: Depth First Search (Postorder Traversal) (Time: O(n), Space: O(h))

This is the optimal approach used in most interview solutions. Traverse the tree using DFS in postorder. For every node, compute the height of its left and right subtrees. The candidate diameter passing through that node is leftHeight + rightHeight. Maintain a global maximum while returning the subtree height as 1 + max(leftHeight, rightHeight). Each node is visited exactly once, so the time complexity is O(n), and recursion stack usage is O(h), where h is the tree height.

This method works because the longest path in a binary tree must pass through some node as the highest point of the path. DFS allows you to compute subtree heights while updating the best diameter in a single traversal. It's simple, efficient, and the expected approach in most coding interviews involving tree traversal.

Approach 2: Dynamic Programming with Memoization (Time: O(n), Space: O(n))

This approach separates height calculation and diameter evaluation using memoization. First compute the height of every node recursively and store results in a hash map or array keyed by node reference. When evaluating the diameter at a node, look up the cached heights of its left and right children instead of recomputing them. This avoids repeated height calculations that would otherwise make the naive solution O(n²).

The algorithm still performs a traversal of all nodes, keeping overall time complexity at O(n). However, the memoization structure stores subtree heights for every node, increasing auxiliary space usage to O(n) in addition to recursion stack space. This pattern resembles classic depth-first search combined with dynamic programming where intermediate subtree results are cached.

Recommended for interviews: The DFS postorder solution is what interviewers typically expect. It computes height and diameter in a single traversal with minimal space. Implementing it correctly shows strong understanding of recursive tree problems. The memoization version demonstrates awareness of avoiding repeated subtree computations, but the single-pass DFS solution is cleaner and more efficient.