114. Flatten Binary Tree to Linked List

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.

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

Example 3:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Intuition

Approach 1:
Using recursion, maintain a prev node to attach left tree to right part
And right part to null

Approach 2:
Iterative, same as above

Approach 3: 
Morris traversal

Links

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

Video Links

https://www.youtube.com/watch?v=sWf7k1x9XR4&t=587s&ab_channel=takeUforward

Approach 1:

Recursion

C++

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

        flatten(root->right);
        flatten(root->left);

        root->right = prev;
        root->left = nullptr;
        prev = root;
    }
};

Approach 2:

Iterative

C++

class Solution {
public:
    
    void flatten(TreeNode* root) {
        if(root == NULL) return;
        stack<TreeNode*> st;
        st.push(root);

        while(!st.empty()){
            TreeNode* curr = st.top();
            st.pop();

            if(curr->right)
                st.push(curr->right);
            if(curr->left)
                st.push(curr->left);

            if(!st.empty())
                curr->right = st.top();

            curr->left = nullptr;
        }
    }
};

Approach 3:

C++

Approach 4:

C++