Flatten Binary Tree to Linked List medium

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list" in-place. The "linked list" should use the same TreeNode nodes, but uses the right child pointer to connect nodes in a linear order. The left child pointer should always be NULL.

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 = [] Output: []

Steps and Explanation

The core idea is to perform a preorder traversal of the binary tree, keeping track of the previously visited node. During the traversal:

1. Recursively flatten the left subtree: This ensures the left subtree is flattened before we process the right subtree.
2. Connect the tail of the left subtree to the right subtree's root: This links the flattened left subtree to the right subtree.
3. Recursively flatten the right subtree: This ensures the right subtree is also flattened.
4. Update the right pointer of the previously visited node: This links the flattened left subtree (or the root if there's no left subtree) to the previously visited node.

Let's illustrate with Example 1:

1. We start at the root (1).
2. We recursively flatten the left subtree (2, 3, 4). This results in a linked list: 2->3->4.
3. We connect the tail of the flattened left subtree (4) to the right subtree's root (5). The structure becomes: 2->3->4->5.
4. We recursively flatten the right subtree (5, 6). This results in a linked list: 5->6. (It's already a simple linked list in this case)
5. We set the right pointer of the root (1) to point to the root of the flattened left subtree (2). Then set the left child of 2 to NULL. The final structure is 1->2->3->4->5->6 (where each node uses the right pointer, and all left pointers are NULL)

Code

#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        
        TreeNode* prev = nullptr;
        flattenHelper(root, prev);
    }

private:
    void flattenHelper(TreeNode* root, TreeNode* &prev) {
        if (root == nullptr) return;

        flattenHelper(root->left, prev); // Flatten left subtree

        if (prev != nullptr) {
            prev->right = root; // Connect previous node to current node.
            root->left = nullptr; //Left always null
        }
        prev = root; //Update the previous node.

        TreeNode* originalRight = root->right; //Store the original right subtree.
        flattenHelper(root->right, prev); //Flatten the right subtree.
        
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once during the preorder traversal.
• Space Complexity: O(H) in the worst case, where H is the height of the tree. This space is used by the recursive call stack. In the case of a skewed tree, H can be equal to N, resulting in O(N) space complexity. For a balanced tree, H is O(log N), resulting in O(log N) space complexity.