415. Check if All Leaf Nodes Are at the Same Level

Given a binary tree, print 'Yes' if every leaf node is at the same depth (the root is depth 0), 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 describing the binary tree ('N' marks an absent child). Output: Print 'Yes' if every leaf is at the same depth, otherwise print 'No'.

1 <= number of nodes <= 10^5

A tree with only a SINGLE leaf overall trivially satisfies this property (there's nothing to disagree with) - a quick sanity-check edge case worth keeping in mind.

Check whether every leaf (childless node) in a binary tree sits at exactly the same depth from the root. Brute force: There isn't really a 'slower' approach here - a single traversal tracking depths and comparing leaf depths at the end IS the natural, direct approach; the only choice is DFS versus BFS for the traversal itself. Optimised: A single DFS (or BFS) pass that records the FIRST leaf's depth as a reference, then checks every SUBSEQUENT leaf against that reference (rather than storing all depths and comparing at the end) lets you fail fast the moment a mismatch is found, without waiting to finish the whole traversal.

Do a standard queue-based level-order traversal, but instead of storing every leaf's depth in a list, keep just one variable holding the depth of the first leaf encountered; whenever a later leaf is found at a different depth, the answer is immediately known to be 'No'. This removes the extra list of depths from the brute approach, replacing it with a single integer, though the BFS queue itself can still hold up to O(n) nodes at the widest level of the tree. Time: O(n) Space: O(n)

Traverse depth-first (recursively or with an explicit stack), passing the current depth down; the first time a leaf is reached, store its depth as the expected value, and every subsequent leaf's depth is compared against it, returning false the moment a mismatch is found instead of continuing to explore the rest of the tree. Because DFS's memory use is bounded by the tree's height rather than its width, this uses noticeably less space than BFS on a wide, shallow tree, and the early-exit check avoids unnecessary work once a mismatch is confirmed. Time: O(n) Space: O(h)

Traverse the whole tree (level order or otherwise), and every time a leaf node (no left and no right child) is found, record its depth into a list. Once traversal finishes, check whether every recorded depth is equal, printing 'Yes' or 'No' accordingly. This is correct and simple to reason about, but it keeps an explicit list of every leaf's depth even though only whether they all match actually matters. Time: O(n) Space: O(n)

1. Traverse the tree while tracking each node's depth (root is depth 0). 2. Whenever you reach a node with no children (a leaf), record its depth. 3. After the traversal, check that every recorded leaf depth is identical - if any differ, the answer is No.

Time: O(n) - every node is visited at most once (with the possibility of stopping early on a mismatch). Space: O(h) for the recursion stack.

Test with a single-node tree (trivially 'Yes'), a tree with only one leaf overall, a tree whose leaves sit at different depths (expect 'No'), and a tree with 10^5 nodes for performance.

Be ready to mention the early-exit optimization (comparing against the first leaf's depth as you go, rather than collecting all depths into a list first) as a small but real efficiency improvement worth mentioning.