Flatten Binary Tree to Linked List (In-place)

To flatten this binary tree in-place, I will first clarify that we need the result to follow preorder traversal order using only the right pointers. A naive recursive solution would work but uses O(H) stack space. Given Amazon's focus on resource efficiency, I prefer an iterative approach similar to Morris Traversal to achieve O(1) space complexity. The core logic involves iterating through the tree. For each node, if it has a left child, we locate the rightmost node in that left subtree, which is the immediate predecessor in the flattened list. We then attach the original right subtree of the current node to this predecessor's right pointer. Next, we move the entire left subtree to the right side of the current node and set the left pointer to null. We then proceed to the new right child. For example, consider a root with value 1, left child 2, and right child 3. Node 2 has no children. We find the predecessor of 2, which is itself since it has no left child? No, wait. If 2 had a left child 4, 4 would be the predecessor. In our case, 2 has no left child, so we just move to 3. The algorithm ensures that every node's left pointer becomes null and the right pointer points to the next node in preorder. This avoids recursion depth issues and meets the strict memory constraints often required in backend engineering roles.