109. Preorder Traversal of a Binary Tree

Given a binary tree, print its preorder traversal (the node, then its left subtree, then its right subtree), space-separated. 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 the preorder traversal values, space-separated, on one line.

1 <= number of nodes <= 10^5

Preorder is exactly the order you'd use to SERIALIZE a tree for later reconstruction, since the root always comes before its subtrees - a detail that connects this simple traversal to more advanced tree-reconstruction problems.

Visit every node of a binary tree in the order: the node itself, then its left subtree, then its right subtree. Brute force: There's no 'slower' alternative here - preorder traversal IS the direct, simplest way to visit nodes in this order; the only real choice is recursive versus iterative implementation. Optimised: A recursive implementation directly mirrors the definition (visit, then recurse left, then recurse right); an iterative version uses an explicit stack, pushing the right child before the left child so that popping naturally processes the left child first - both achieve the same O(n) traversal.

Visit the root, then recursively traverse the left subtree, then recursively traverse the right subtree, printing each node's value the moment it's visited. This directly mirrors the definition of preorder traversal and is the simplest correct implementation, but it relies on the call stack, whose depth equals the tree's height - for a fully skewed tree with up to 10^5 nodes that means up to 10^5 stack frames, which risks a stack overflow in many language runtimes. Time: O(n) Space: O(h)

Use threaded binary tree traversal (Morris traversal) to eliminate the stack entirely: for each node, if it has a left child, find its inorder predecessor (the rightmost node of the left subtree) and create a temporary thread from that predecessor back to the current node before descending left; print the current node right before creating the thread (giving preorder order), and remove the thread once you return via it. Every temporary link is undone by the end, so the tree is left unmodified, and the algorithm needs no stack or recursion at all, achieving true O(1) extra space instead of the O(h) needed by the previous two approaches. Time: O(n) Space: O(1)

Simulate the same recursive process with your own stack: push the root, then repeatedly pop a node, print it, and push its right child followed by its left child (so the left child is popped first). This produces the identical output as the recursive version but replaces the implicit call stack with an explicit one you control, which avoids language-level recursion-depth limits and stack-overflow risk on deeply skewed trees, while keeping the same time and space bounds. Time: O(n) Space: O(h)

1. Visit (print) the current node first. 2. Recursively traverse the entire left subtree the same way. 3. Recursively traverse the entire right subtree the same way.

Time: O(n) - every node is visited exactly once. Space: O(h) for the recursion stack (or explicit stack), where h is the tree's height - O(n) in the worst case of a skewed tree, O(log n) for a balanced one.

Test with a single-node tree, a tree that is entirely left-skewed or entirely right-skewed, and a tree with 10^5 nodes for performance.

Be ready to implement BOTH the recursive and iterative (stack-based) versions - interviewers often specifically ask for the iterative one to test comfort with explicit stack management.