Flatten Binary Tree to Linked List — Morris Traversal

Problem 242 · Flatten Binary Tree to Linked List

Difficulty: Medium · Pattern: Morris-Style In-Place

Flatten tree to right-linked list in pre-order, in-place with O(1) extra space.

Approach

For each node with a left child:

Find rightmost node of left subtree (the "predecessor")
Connect it to node.right
Move node.left to node.right; set node.left = null

Solutions

# Python — O(1) space Morris-style
def flatten(root):
    cur = root
    while cur:
        if cur.left:
            # Find rightmost of left subtree
            pre = cur.left
            while pre.right: pre = pre.right
            pre.right = cur.right
            cur.right = cur.left
            cur.left = None
        cur = cur.right

// Java
public void flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null) {
            TreeNode pre = cur.left;
            while (pre.right != null) pre = pre.right;
            pre.right = cur.right;
            cur.right = cur.left;
            cur.left = null;
        }
        cur = cur.right;
    }
}

// C++
void flatten(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (cur->left) {
            TreeNode* pre = cur->left;
            while (pre->right) pre = pre->right;
            pre->right = cur->right;
            cur->right = cur->left;
            cur->left = nullptr;
        }
        cur = cur->right;
    }
}

Complexity

Time: O(n)
Space: O(1)