108. Inorder Traversal of a Binary Tree

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

1 <= number of nodes <= 10^5

Inorder, preorder, and postorder are all the SAME basic recursive shape, differing only in WHEN the current node is visited relative to its two subtree recursions - mastering one makes the other two nearly automatic.

Visit every node of a binary tree in the order: left subtree, then the node itself, then right subtree. Brute force: There's no meaningfully 'slower' alternative - inorder traversal IS the direct definition; the only real choice is recursive versus iterative (stack-based) implementation. Optimised: An iterative version uses an explicit stack: push left children repeatedly until hitting a dead end, then pop-visit-and-move-right - this achieves the same O(n) traversal without relying on the call stack, useful when recursion depth could be a concern for very deep trees.

Build the binary tree from the level-order token list, then write a straightforward recursive function that visits the left subtree, prints/records the current node's value, then visits the right subtree. This directly mirrors the definition of inorder traversal and is correct by construction. It relies on the call stack to remember where to return to after each subtree finishes. Time: O(n) Space: O(h) recursion stack (O(n) worst case for a skewed tree)

Simulate the recursion manually using an explicit stack: repeatedly push the current node and move left until hitting null, then pop a node, record its value, and move to its right child. This avoids relying on the language's call stack, so it can't overflow on a very deep (skewed) tree, and gives more control over the traversal for later augmentation (e.g. iterative resumption). It's algorithmically the same visiting order as the recursive version but implemented with an explicit data structure. Time: O(n) Space: O(h) (O(n) worst case)

Use Morris traversal: for each node without a left child, visit it and move right; otherwise find the current node's inorder predecessor (rightmost node of its left subtree) and create a temporary 'thread' link from that predecessor back to the current node, then descend left. When traversal returns to a node via its thread, that thread is removed (restoring the tree) and the node is visited before moving right. This eliminates the need for any stack or recursion entirely by temporarily repurposing null right-pointers, achieving true O(1) auxiliary space, which matters a great deal at n up to 10^5. Time: O(n) Space: O(1)

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

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.

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 explain WHY inorder traversal specifically produces ascending values on a BST - this connects the simple traversal directly to numerous BST-specific problems (kth smallest, validate BST, and more).