409. Boundary Traversal of a Binary Tree

Given a binary tree, print its boundary values in this order: the root; then the left boundary top-to-bottom (every node on the path from the root's left child downward, always preferring the left child and falling back to the right child, but skipping any node that is itself a leaf); then every leaf left to right; then the right boundary bottom-to-top (the mirror of the left boundary, again skipping leaves), all space-separated on one line, with no value repeated. If the root has no children at all, print just the root. 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 the boundary values - root, left boundary top-to-bottom, all leaves left to right, right boundary bottom-to-top - space-separated on one line with no value repeated.

1 <= number of nodes <= 10^5

The special case of a root with NO children at all reduces to simply printing just the root - both boundary walks and the leaf collection would otherwise all trivially point to the same single node, so this needs an explicit early check to avoid duplicate printing.

Print a binary tree's outer boundary: the root, then the left edge going down, then all the leaves, then the right edge going back up - each value printed exactly once. Brute force: Do a full traversal and try to classify every single node as 'boundary' or 'not' with complex conditional logic checked node-by-node - this is error-prone and hard to get exactly right; splitting the problem into three clean, separate sub-walks (left boundary, leaves, right boundary) is far more manageable. Optimised: Treating the boundary as three CLEANLY SEPARATE walks (a left-boundary DFS that skips leaves, a plain leaf-collecting traversal, and a right-boundary DFS that also skips leaves but gets reversed before printing) avoids any node being counted twice and keeps each sub-walk's logic simple and independently verifiable.

Perform the same three-part logic (left boundary skipping leaves, leaf collection, reversed right boundary skipping leaves), but implement each part iteratively with an explicit stack instead of recursive function calls. This produces identical output to the recursive version but bounds the auxiliary control structures more predictably and avoids relying on the language call stack, which is a meaningful safeguard here since the tree can have up to 10^5 nodes and a skewed shape could otherwise risk deep recursion. Time: O(n) Space: O(n)

Collect the root, then recursively walk the left boundary top-down while explicitly skipping any node that is itself a leaf, separately collect all leaves left to right with a simple traversal, then recursively walk the right boundary and reverse it before appending, again skipping leaf nodes along that path. Because leaves are deliberately excluded from the left/right boundary walks by construction (rather than by after-the-fact filtering), no node is ever collected twice, so the hash-set bookkeeping from the brute-force version becomes unnecessary while still visiting each node a constant number of times. Time: O(n) Space: O(n)

Run three completely independent full traversals of the tree: one that walks down checking at each node whether it lies on the leftmost path to collect the left boundary, one that walks the whole tree collecting every leaf, and one that walks down the rightmost path to collect the right boundary; then concatenate the three lists while using a hash set to filter out any node that got captured more than once (since a leaf on the boundary path could otherwise be printed twice). This is correct but pays for three separate full walks of the tree plus extra membership checks purely to avoid duplicate output. Time: O(n) Space: O(n)

1. Print the root first. 2. Walk the LEFT boundary top-to-bottom: from the root's left child downward, always preferring the left child but falling back to the right child if no left child exists - skipping any node that is itself a leaf (leaves get collected separately). 3. Collect and print ALL leaves, left to right, via a normal traversal. 4. Walk the RIGHT boundary the same way as the left (mirrored), but print it BOTTOM-TO-TOP - so collect it top-to-bottom like the left boundary, then REVERSE that list before printing.

Time: O(n) - each of the three sub-walks visits a bounded portion of the tree, and the leaf-collection walk visits every node once. Space: O(n) in the worst case, for the boundary and leaf lists collected before final printing.

Test a single-node tree (print just the root), a root whose children are both leaves themselves, and a tree with only a left subtree or only a right subtree (the empty side contributes nothing).

Be ready to clarify the exact 'skip leaves in the boundary walks' rule - this is what prevents leaves from being printed TWICE (once as part of a boundary walk, and again in the dedicated leaf-collection step), a very common bug in first attempts at this problem.