106. Diameter of a Binary Tree

Given a binary tree, find its diameter - the number of nodes on the longest path between any two nodes in the tree (the path may or may not pass through the root). The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens ('N' for missing children) describing the binary tree. Output: Print a single integer - the diameter (the number of nodes on the longest path between any two nodes).

1 <= number of nodes <= 10^5

Computing height and checking diameter in the SAME single pass (rather than one pass for heights, then a separate pass checking every node's diameter) is what keeps this O(n) instead of O(n²) - a very common efficiency trap in this exact problem.

Find the longest path (by node count) between ANY two nodes in a binary tree - the path might not pass through the root at all. Brute force: For every pair of nodes, compute the path length between them directly (via their LCA and depths) - this costs O(n²) or worse, far more than necessary given a much simpler bottom-up height computation. Optimised: Since the diameter THROUGH any given node depends only on its two children's HEIGHTS (which you're already computing bottom-up anyway for the tree's overall height), tracking a running 'best diameter seen at any node' as a side effect of a single height-computing post-order pass finds the answer with no extra traversals.

For every node in the tree, call a separate height() function on its left child and another on its right child, add the two heights together as a candidate diameter through that node, and take the maximum candidate over all nodes (visited via any traversal). Because height() itself recurses through an entire subtree and gets called anew at every ancestor above it, the same subtrees get re-measured many times, giving quadratic behavior on a skewed tree. Time: O(n^2) Space: O(h)

Write one recursive function that, for each node, first recurses into the left and right children to get their heights, updates a shared "best diameter so far" value with leftHeight + rightHeight at this node, and then returns 1 + max(leftHeight, rightHeight) as this node's own height to its parent. Because height and diameter are computed together in the same single post-order walk, no node's subtree is ever revisited and no separate storage of heights is needed beyond the recursion stack. Time: O(n) Space: O(h)

First do one bottom-up (post-order) traversal that computes and stores the height of every node in a hash map, without touching the diameter yet. Then do a second traversal (any order) that, for each node, looks up its precomputed left-height and right-height from the map, sums them, and updates a running maximum. Splitting height computation from diameter computation into two full linear passes with stored intermediate results avoids the repeated re-measuring the brute approach does. Time: O(n) Space: O(n)

1. For EVERY node, the longest path passing THROUGH it equals height(its left subtree) + height(its right subtree) + 1 (for the node itself). 2. Compute heights bottom-up in a single post-order pass, and at each node, check if the path THROUGH it beats the best diameter found so far. 3. The overall answer is the best such value found across every single node, not just the root.

Time: O(n) - one single post-order pass, computing heights and checking diameter-through-this-node simultaneously at every node. Space: O(h) for the recursion stack.

Test a single-node tree (diameter 1), a fully skewed tree (a straight line, diameter equal to the node count), a tree whose longest path doesn't pass through the root, and n=10^5 for performance.

Be ready to explain explicitly why the diameter DOESN'T need to pass through the root - a common naive-but-wrong first instinct is computing only height(root's left)+height(root's right)+1, missing diameters entirely contained within a subtree.