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.


&nbsp;
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]


&nbsp;
Constraints:


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


&nbsp;
Follow up: Can you flatten the tree in-place (with O(1) extra space)?
#Call the right of the tree node till the node root left and right is not None
#After reaching the bottom of the tree make the root.right = prev and
#root.left = None and then prev = None
#Initially prev will point to None but this is used to point the previously visited root node
#Prev pointer helps us to change the values from left to right
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        prev = None #You can also define that variable inside the init function using self keyword
        def dfs(root):
            nonlocal prev

            if not root:
                return

            dfs(root.right)
            dfs(root.left)

            root.right = prev
            root.left = None
            prev = root

        dfs(root)
# If the above solution is hard to understand than one can do level order traversal
#Using Stack DS but this will increase the space complexity to O(N).
class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr=root;
        while(curr!=null)
        {
            if(curr.left!=null)
            {
               TreeNode prev=curr.left;
               while(prev.right!=null)
                   prev=prev.right;
               prev.right=curr.right;
               curr.right=curr.left; 
               curr.left=null; 
            }
            curr=curr.right;
        }
    }
}
class Solution {
public:
    TreeNode* prev= NULL;
    
    void flatten(TreeNode* root) {
        if(root==NULL) return;
        
        flatten(root->right);
        flatten(root->left);
        
        root->right=prev;
        root->left= NULL;
        prev=root;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    const dfs = (node) => {
        if (!node) return

        if (!node.left && !node.right) return node

        const leftNode = node.left
        const rightNode = node.right

        const leftTree = dfs(leftNode)
        const rightTree = dfs(rightNode)

        if (leftTree) leftTree.right = rightNode

        node.left = null
        node.right = leftNode || rightNode

        return rightTree || leftTree
    }

    dfs(root)
    return root
};
Flatten Binary Tree to Linked List