411. Convert a Binary Tree Into a Doubly Linked List

Given a binary tree, thread it into a doubly linked list following inorder order: the leftmost node's inorder becomes the head, each node's 'next' pointer leads to its inorder successor, and each node's 'prev' pointer leads to its inorder predecessor. Print the list twice to prove both directions were wired correctly: first head-to-tail (following 'next'), then tail-to-head (following 'prev'), each traversal space-separated on its own line. 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 two lines: the list traversed head-to-tail via 'next' pointers (the inorder sequence), then the same list traversed tail-to-head via 'prev' pointers, each space-separated.

1 <= number of nodes <= 10^5

This is conceptually the same 'relink nodes during inorder traversal' technique used in 'Flatten a BST to a Sorted List' - the only difference is maintaining BOTH next and prev pointers here, instead of only a one-directional right-child chain.

Thread a binary tree's nodes into a doubly linked list following inorder order - each node's 'next' points to its inorder successor, and 'prev' to its inorder predecessor. Brute force: First collect all values via inorder traversal into an array, then build an entirely new doubly linked list from that array, discarding the original tree nodes - this works but does unnecessary extra allocation when existing nodes can simply be relinked in place. Optimised: Since inorder traversal already visits nodes in the target order, relinking each node's own next/prev pointers AS YOU TRAVERSE (tracking just one 'previous node' reference) achieves the threading with a single pass and no extra node allocation.

Perform a standard recursive inorder traversal that simply appends each visited node's reference into an array/list, exactly reproducing inorder order without altering any pointers yet. Then make a second pass over that array, setting array[k].next = array[k+1] and array[k+1].prev = array[k] for every consecutive pair. This is easy to get right because collection and linking are fully separated, but it pays for an extra array holding every node reference. Time: O(n) Space: O(n)

Use Morris inorder traversal: when a node has a left subtree, temporarily rewire the rightmost node of that left subtree's right pointer to point back to the current node (a "thread") so that after visiting the left subtree, control returns to the current node without a stack; wire prev.next/current.prev links as each node is visited in order, then remove each thread once it's been used to move on. This achieves the exact same threading result as the recursive version but needs neither a recursion stack nor an explicit list, since the tree's own (temporarily repurposed) pointers do the traversal bookkeeping. Time: O(n) Space: O(1)

Do a single recursive inorder traversal, but instead of collecting nodes into a list, carry a "previously visited node" reference through the recursion (e.g. as a value captured by the closure or passed by reference). When visiting a node, link it to the previous node (prev.next = current, current.prev = prev) if one exists, otherwise mark it as the head, then update "previous" to the current node before recursing right. This removes the need for the intermediate array entirely, using only the recursion stack. Time: O(n) Space: O(h)

1. Do an inorder traversal while keeping track of the PREVIOUSLY visited node. 2. As you visit each new node, link previous.next = current AND current.prev = previous. 3. The very first node visited becomes the list's head (no prev); the very last node visited becomes the tail (no next).

Time: O(n) - one single inorder traversal, relinking pointers as you go. Space: O(h) for the recursion stack if done recursively, or O(1) extra with an iterative Morris-traversal-based approach.

Test a single-node tree (both lines contain just that one value), and n=10^5 nodes for performance since both directions come from a single linking pass.

Be ready to explain that the tail-to-head sequence is EXACTLY the reverse of the head-to-tail sequence - both are the same inorder sequence, just traversed in opposite directions using the prev/next pointers respectively.