Flatten a binary tree

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 rightchild 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 traversalof 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

Solution:

1. Not Space Optimized:

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
 
        Queue<TreeNode> q = new LinkedList<>();
        flatten_(root, q);
        
        TreeNode curr = q.poll();
        curr.right = q.poll();
        
        buildTree(q, curr.right);
        root.left = null;
        root.right = curr.right;
    }
 
    public void buildTree(Queue<TreeNode> q, TreeNode root){
        if(q.isEmpty()) return;
        
        root.right = q.poll();
        root.left = null;
 
        buildTree(q, root.right);
    }
 
    public void flatten_(TreeNode root, Queue<TreeNode> q) {
        if(root == null){
            return;
        }
 
        q.add(root);
        flatten_(root.left, q);
        flatten_(root.right, q);
    }
}

2. Space Optimized:

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten_(root);
    }
 
    private void flatten_(TreeNode node) {
        if (node == null) {
            return;
        }
 
        TreeNode left = node.left;
        TreeNode right = node.right;
 
        node.left = null;
 
        flatten_(left);
        flatten_(right);
 
        node.right = left;
        TreeNode curr = node;
        while (curr.right != null) {
            curr = curr.right;
        }
        curr.right = right;
    }
}