Flatten Binary Tree to Linked List LeetCode Solution says that – 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]

ALGORITHM –

IDEA –

• In order to flatten a binary tree, we will first find the rightmost element of the left subtree and after we got the rightmost element we will link the right-pointer of that node with a right subtree of a given tree.
• In step 2 we will link the right pointer of the root node with the left-subtree and set the left-subtree as null.
• In step 3 now our root node is a right-subtree node same process will happen with this node and the process will still continue until all the left parts become null.

Approach for Flatten Binary Tree to Linked List Leetcode Solution –

– At first, i will run a loop i.e. while(root != null) then will take two variables and store the left-subtree.

– then will check check for the rightmost node of left-subtree by using while(k.left != null) and will link that node with right subtree using (k.right = root.right).

– then link  right pointer of root node with left subtree(root.right = left) and set left pointer of root node as null(root.left=null) and will update by ( root = root.right ) so now root is right subtree node.

– this process will continue until all left-subtree parts become right subtree. Hence, the binary tree will get flattened.

Python Solution:

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

Java Solution:

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

Time complexity: O(N)

Space Complexity: O(1)

As we have traversed only once, time complexity will be o(n).

and as we haven’t taken any extra space, space complexity will be o(1) constant extra space.

Similar Question – https://tutorialcup.com/interview/linked-list/flattening-linked-list.htm