Trees - Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree in-place into a linked list (using right pointers, in preorder traversal order).

Input: root=[1,2,5,3,4,null,6] → Output: [1,null,2,null,3,null,4,null,5,null,6]

Input: root=[0] → Output: [0]

Process each node: find the rightmost node of the left subtree (the preorder predecessor of the right subtree), attach right subtree there, then move left subtree to the right.

While root != null:
If root.left != null: find rightmost of left subtree.
Attach root.right to that rightmost node's right.
Move root.left to root.right, set root.left = null.
Advance root = root.right.

class Solution { public void flatten(TreeNode root) { while (root != null) { if (root.left != null) { TreeNode rightmost = root.left; while (rightmost.right != null) rightmost = rightmost.right; rightmost.right = root.right; root.right = root.left; root.left = null; } root = root.right; } } }

Time Complexity: O(N)
Space Complexity: O(1)