DAY 62 - Flatten a Binary Tree into a linked list

Question: Flatten a Binary Tree into a linked list

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]

Intuition:

• Let's get the question clear first. We need to convert the binary tree into a linked list. We don't have to create another node which represents a linked list but using the current properties of a binary tree we need to create a linked list representation.
• We are going to use here a traversal known as morriss traversal. To read more about it I recommend reading this Morris Traversal.
• How are we applying it here. To eliminate the need of recursion stack or normal stack, we can solve this question in constant time complexity using Morris Traversal.
• If we see carefully. We can see that the last node that will be visited in the preOrder traversal of left subtree is going to connect to the first node of right subtree.
• In this case 4 is the last node and 5 is the first node, So we connect them.
• Our left subtree will come first and we simply need to attach that to our cur node.
• So we put the cur->right = cur->left and make left pointer of current node null.
• We repeat this process until our cur is null.

Algorithm & Code:

Algorithm:

Initialization:

• The function takes the root of the binary tree as input.
• It initializes two pointers, cur and prev, to keep track of the current node and the previous node in the flattened structure, respectively.
• Initially, cur is set to the root of the binary tree, and prev is set to NULL.

Flattening Process:

• While cur is not NULL, the function performs the following steps:
• If the current node (cur) has a left child:
• The function moves prev to the rightmost node of the left subtree of cur. This is done by repeatedly traversing the right pointers until reaching the rightmost node (prev now points to the rightmost node).
• The right child of the rightmost node (prev->right) is set to the right child of the current node (cur->right). This effectively attaches the right subtree of the current node to the rightmost node of its left subtree.
• The left child of the current node (cur->left) is set to NULL, as the left subtree is now part of the flattened structure.
• The function then moves cur to its right child, effectively moving to the next node in the binary tree.

Code:

/**
 * Definition for a binary tree node.
 * 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:
    TreeNode* prev = NULL;
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while(cur != NULL){
            if(cur->left != NULL){
                prev = cur->left;
                while(prev->right){
                    prev = prev->right;
                }
                prev->right = cur->right;
                cur->right = cur->left;
                cur->left = NULL;
            }
            cur = cur->right;
        }
    }
};

Complexity Analysis:

Time: O(N)
Space: O(1)