122. Maximum Width of a Binary Tree

Given a binary tree, find the maximum number of nodes present at any single level, and print that count. 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 maximum number of nodes present at any single level.

1 <= number of nodes <= 10^5

This problem's specific definition (count of NODES PRESENT at a level, ignoring gaps) is simpler than the 'positional span including missing nodes' variant sometimes seen elsewhere - always read the exact definition given rather than assuming the harder variant.

Find the largest number of nodes present at any single level of a binary tree. Brute force: Compute the depth of every single node via a full traversal, then bucket-count nodes by depth and find the largest bucket - this works but is more indirect than simply counting during a level-order traversal, which already naturally groups nodes by level. Optimised: A single level-order (BFS) traversal already processes nodes ONE LEVEL AT A TIME (using the 'process the current queue size, then move to the next level' technique) - counting nodes per level as you go and tracking the maximum requires no extra bucketing or depth computation at all.

Parse the level-order tokens into an actual tree structure, then do one DFS pass while tracking the current depth of each node, incrementing a counter in a depth-indexed map/array as each node is visited, and finally scan that map for its maximum value. This only touches every node once instead of re-scanning per level, a clear improvement over the repeated-DFS brute force, though it needs auxiliary storage for the per-level counts and the DFS recursion stack. Time: O(n) Space: O(n)

Process the level-order token stream with a queue, building each node's children as they're dequeued while simultaneously tracking how many nodes are enqueued for the next level, updating the maximum width as each level completes, all in one fused build-and-traverse pass. This avoids the separate DFS recursion of the better approach, which matters since n can be up to 10^5 and a deep, skewed tree could otherwise risk deep recursion; BFS with an explicit queue keeps memory proportional to the widest level rather than the tree's height. Time: O(n) Space: O(w), w = widest level

For each candidate depth d starting from 0, do a full DFS/BFS pass over the tree counting only nodes at exactly depth d, stop increasing d once a pass finds zero nodes, and keep track of the largest count seen. This is correct because it directly counts every level, but it re-traverses large portions of the tree once per level, which is wasteful when the tree is tall and skewed. Time: O(n * h), O(n^2) worst case for a skewed tree Space: O(h)

1. Do a level-order (breadth-first) traversal. 2. For each level, count how many actual (non-null) nodes are present. 3. Track and report the largest such count seen across all levels.

Time: O(n) - one single BFS pass, every node counted exactly once. Space: O(n) in the worst case, for the BFS queue (a very wide level, like a complete binary tree's bottom row).

Test a single-node tree (width 1), a perfectly complete tree whose deepest level holds the most nodes, and n=10^5 nodes for performance.

Be aware that some variants of 'maximum width' define it based on the span between the leftmost and rightmost node's POSITIONS (including gaps from missing nodes), not just a plain count of present nodes - always clarify which definition a given problem is using, since this problem explicitly asks for the simple count.