Flatten Binary Tree to Linked List - Solution & Explanation

This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.

The steps are as follows:

1. Recursively flatten the left and right subtrees.
2. Save the right subtree, then set the root's right to the left subtree and left to null.
3. Traverse to the end of the new right subtree (originally left subtree) and append the saved right subtree.

This leverage the pre-order traversal principle: Root → Left → Right.

This code defines a flatten function for recursively transforming a binary tree into a linked list in pre-order format. It first flattens the left and right subtrees, then rearranges the pointers of the root node.

This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.

The algorithm progresses with these steps:

1. Construct a stack and push the root.
2. Process nodes using a stack to handle traversal iteratively, similar to pre-order.
3. While processing each node, capture its left and right children, alter pointers, and advance the iteration.

This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.

This C code leverages a custom stack to iteratively implement pre-order traversal. Nodes are processed such that when a node is visited, it pushes its right and left children onto the stack. The list is reordered inline using right field connections.