114. Flatten Binary Tree to Linked List

Intuition

To flatten the tree, we need to rearrange its nodes such that the left subtree of each node is moved to the right, and the original right subtree is appended to the end of this new right subtree. The transformation should maintain the order of nodes as they would appear in a pre-order traversal.

Approach

1. Traverse the tree using a pointer curr.
2. For each node, if there is a left subtree: - Find the rightmost node in the left subtree (runner). - Attach the right subtree of curr to the rightmost node in the left subtree. - Move the left subtree to the right and set the left to None.
3. Move curr to the right child.
4. Repeat until the entire tree is flattened.

Complexity

Time complexity:

O(n), where n is the number of nodes in the tree. Each node is visited once.

Space complexity:

O(1), as the solution uses a constant amount of extra space.

Code

C++

class Solution 
{
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;
        while (curr) {
            if (curr->left) {
                TreeNode* runner = curr->left;
                while (runner->right) {
                    runner = runner->right;
                }
                runner->right = curr->right;
                curr->right = curr->left;
                curr->left = nullptr;
            }
            curr = curr->right;
        }
    }
};

Python

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        
        curr = root
        while curr:
            if curr.left:
                runner = curr.left
                while runner.right:
                    runner = runner.right
                runner.right = curr.right
                curr.right = curr.left
                curr.left = None
            curr = curr.right

Java

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

JavaScript

var flatten = function (root) 
{
    let curr = root
    while (curr) 
    {
        if (curr.left) {
            let runner = curr.left
            while (runner.right) runner = runner.right
            runner.right = curr.right, curr.right = curr.left, curr.left = null
        }
        curr = curr.right
    }
};