117. Check if a Binary Tree Is Height-Balanced

Given a binary tree, print 'Yes' if it is height-balanced - meaning for every node, the heights of its left and right subtrees differ by at most 1 - otherwise print 'No'. 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 'Yes' if the tree is height-balanced at every node, otherwise print 'No'.

1 <= number of nodes <= 10^5

A common efficient trick is having the height-computing function return a SENTINEL value (like -1) the moment an imbalance is detected anywhere below, letting the check short-circuit all the way up without needing a separate boolean flag threaded through the recursion.

Check whether, at every single node in a binary tree, the heights of its left and right subtrees differ by at most 1. Brute force: For every node, separately compute its left and right subtree heights from scratch by re-traversing them - this recomputes overlapping heights repeatedly, costing O(n²) in the worst case (a very skewed tree). Optimised: Computing height and checking balance in the SAME bottom-up post-order pass avoids ever recomputing a subtree's height more than once - each node's height is computed exactly once and immediately reused for both the balance check and the parent's own height computation.

For every node in the tree, independently call a standalone height() function on its left child and on its right child, compare the two heights, and recurse the same balance check into both children. Because height() itself walks an entire subtree from scratch, and it gets called again for every node above it, the same nodes end up having their heights recomputed many times over the course of the whole check. Time: O(n^2) Space: O(h)

Do a single post-order recursion that returns a node's height as normal, but the instant it detects an imbalance anywhere in a subtree (its own children's heights differing by more than 1, or a child recursion already reporting imbalance) it returns a special sentinel value such as -1 that propagates straight up and short-circuits all further work in that branch. This needs no auxiliary hashmap at all - only the O(h) recursion call stack - and, unlike the better approach, it can stop early on unbalanced trees instead of finishing every height computation before checking balance, so it is both leaner in space and faster in practice on skewed inputs. Time: O(n) Space: O(h)

First do one full post-order traversal that computes the height of every node exactly once and stores it in a hashmap keyed by node. Then do a second traversal that, for every node, simply looks up its children's heights in the map and checks that they differ by at most 1. Because each height is computed only once and reused via lookup instead of being recomputed by repeated recursive calls, the height-computation cost drops from quadratic to linear, at the price of extra memory to store every node's height. Time: O(n) Space: O(n)

1. Compute height BOTTOM-UP (post-order), and at every node, check whether its own left and right subtree heights differ by more than 1. 2. Do this CHECK in the SAME pass as the height computation, so you don't waste time recomputing heights separately for a check afterward. 3. The moment ANY subtree is found unbalanced, you can short-circuit and immediately report the whole tree as unbalanced.

Time: O(n) - one single post-order pass with combined height computation and balance checking. Space: O(h) for the recursion stack.

Test a single-node tree (trivially balanced), a fully skewed tree (becomes unbalanced once it has 3+ nodes), a tree balanced everywhere except one deep subtree, and n=10^5 for performance.

Be ready to explain the naive O(n²) approach's exact inefficiency (recomputing height from scratch at every node for the check) versus the O(n) combined approach - clearly articulating this difference is a strong signal.