Flatten Binary Tree to Linked List

Share

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

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

Solution Approach

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.
Java
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)