104. Height of a Binary Tree

Given a binary tree, print its height, counted as the number of nodes on the longest path from the root to any leaf (a single-node tree has height 1). 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 describing the binary tree ('N' marks an absent child). Output: Print a single integer - the tree's height.

1 <= number of nodes <= 10^5

This exact height computation is a building block reused constantly elsewhere (checking if a tree is height-balanced, computing diameter, and more) - mastering this simple recursive shape pays off broadly.

Find the number of nodes along the longest path from the root down to any leaf. Brute force: There isn't really a slower alternative - computing height IS inherently a bottom-up recursive computation; the only variation is doing it recursively (natural) versus iteratively with an explicit level-by-level (BFS) count. Optimised: A single post-order recursive pass (computing children's heights before combining them) computes the whole tree's height in one traversal - no need to separately measure every root-to-leaf path, since the recursive formula naturally captures 'the longest path so far, extended by one more step upward'.

Traverse the tree level by level using a queue: start with just the root in the queue, and repeat the process of draining every node currently in the queue for the current level (enqueueing each of their children as they're dequeued) while incrementing a height counter once per fully processed level. Once the queue empties, the counter holds the tree's height. This needs a queue that can hold as many nodes as the widest level of the tree, which in the worst case (a very bushy tree) can be proportional to the whole node count. Time: O(n) Space: O(n) worst case (widest level)

Perform a depth-first traversal that, at every leaf reached, records the entire sequence of nodes from the root down to that leaf as one complete path, collecting every such path into a list. Once every leaf has been visited this way, scan the collected paths and report the length of the longest one as the tree's height. Because full paths are stored in their entirety even though many of them share long common prefixes near the root, this uses far more memory and time than necessary, especially on tall, skewed trees. Time: O(n * h) (h = tree height, up to n for skewed trees) Space: O(n * h)

Compute height(node) recursively as 0 for a null node, otherwise 1 plus the larger of height(node.left) and height(node.right); the answer is height(root). Since every node is visited exactly once and does only constant work beyond its two recursive calls, this is linear in the number of nodes, and the extra memory needed is just the recursion (or explicit) stack depth, which equals the height of the tree - at most n for a completely skewed tree, but only O(log n) for a balanced one, making it more memory-efficient than the level-order approach on wide, shallow trees. Time: O(n) Space: O(h) (h = tree height)

1. Recursively compute the height of the left subtree and the height of the right subtree. 2. The current node's height is 1 plus whichever of the two is larger. 3. An empty (missing) subtree contributes a height of 0, forming the base case.

Time: O(n) - every node is visited exactly once. Space: O(h) for the recursion stack, where h is the height itself - O(n) worst case for a skewed tree.

Test with a single-node tree (height 1), a completely skewed tree (height equals node count), and a tree with 10^5 nodes for performance.

Be precise about the exact height DEFINITION being used (nodes on the path, versus edges on the path) - this problem explicitly defines a single-node tree as height 1 (counting nodes), which is a common source of off-by-one confusion versus the edge-counting convention.