123. Count Leaf Nodes in a Binary Tree

Given a binary tree, count and print the number of leaf nodes (nodes with no children). 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 total number of leaf nodes.

1 <= number of nodes <= 10^5

A node with only ONE child (not both absent) is NOT a leaf - a subtle but important distinction from 'has at least one missing child'.

Count how many nodes in a binary tree have absolutely no children. Brute force: There isn't a meaningfully different 'slower' approach - a single traversal checking each node for the leaf condition IS the natural and direct approach. Optimised: A single recursive (or iterative BFS/DFS) pass, incrementing a counter exactly when both children are absent, counts every leaf in one traversal with no redundant work.

Use Morris traversal to visit every node without any recursion or explicit stack/queue at all: for each current node, if it has a left child, find its inorder predecessor (the rightmost node in its left subtree) and temporarily thread that predecessor's right pointer to point back to the current node, using this thread to return later and then removing it once traversed; nodes with no children are counted as leaves along the way. This achieves the same linear time as DFS or BFS but uses only a constant number of extra pointers rather than a stack, queue, or recursion, which is the best possible space bound for this problem. Time: O(n) Space: O(1)

Recursively visit each node: if it has no left and no right child, it's a leaf, so add one to the running count; otherwise recurse into whichever children exist and sum their leaf counts. This still visits every node exactly once, but the auxiliary space used is now the recursion call stack, which is bounded by the tree's height rather than its width - for a reasonably balanced tree that's a logarithmic amount of memory instead of the BFS queue's potentially linear width. Time: O(n) Space: O(h)

Rebuild the tree from the level-order tokens, then traverse it breadth-first using an explicit queue: dequeue a node, and if it has neither a left nor a right child, count it as a leaf, then enqueue any existing children. This visits every node exactly once, but in the worst case (a wide, bushy tree) the queue can simultaneously hold up to roughly half the nodes, at the last level. Time: O(n) Space: O(n)

1. Recursively traverse the tree. 2. Whenever you reach a node with BOTH children absent, increment a leaf counter. 3. Sum this up across the whole tree.

Time: O(n) - every node is visited exactly once. Space: O(h) for the recursion stack.

Test a single-node tree (the root itself is the only leaf, answer 1), a fully skewed tree (exactly one leaf), and n=10^5 nodes for performance.

This is typically a warm-up question - the real value is confirming you handle the base case (a single-node tree with no children, which is itself trivially one leaf) correctly.