Flatten Binary Tree to Linked List

mediumAmazon-tagged: Trees & Matrix (mock day)34 stepsJava · Python · C++

Flatten a tree into a right-leaning list in preorder, in place. For each node with a left child, find the rightmost node of its left subtree, attach the node's right subtree there, then move the left subtree to the right. Continue down the right pointers.

▶ Watch the animated trace

Traced input: root = [1, 2, 5, 3, 4, null, 6] → [1,null,2,null,3,null,4,null,5,null,6]. Original problem: leetcode.com/problems/flatten-binary-tree-to-linked-list/

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Each edge is walked a constant number of times; no recursion stack.

Key idea

In preorder, the right subtree comes right after the last node of the left subtree.
That last node is the rightmost node of the left subtree.
Splice: rightmost.right = node.right; node.right = node.left; node.left = null.

Common mistakes

Forgetting to set left = null.
Recursive solutions work but use O(h) stack.

Solution

Java

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

Python

def flatten(root: Optional[TreeNode]) -> None:
    node = root
    while node:
        if node.left:
            rightmost = node.left
            while rightmost.right: rightmost = rightmost.right
            rightmost.right = node.right
            node.right = node.left
            node.left = None
        node = node.right

C++

void flatten(TreeNode* root) {
    TreeNode* node = root;
    while (node) {
        if (node->left) {
            TreeNode* rightmost = node->left;
            while (rightmost->right) rightmost = rightmost->right;
            rightmost->right = node->right;
            node->right = node->left;
            node->left = nullptr;
        }
        node = node->right;
    }
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty tree Nothing to do.	`root = []`	`[]`
Already flat No left children to move.	`root = [1, null, 2, null, 3]`	`[1,null,2,null,3]`
Left chain Each left child swings to the right.	`root = [1, 2, null, 3]`	`[1,null,2,null,3]`