114. Flatten Binary Tree to Linked List

Description

Given a binary tree, flatten it to a linked list in-place.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, 2, 5, 3, 4, null, 6]

Output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
 
        while(p != null || !stack.empty()){
 
            if(p.right != null){
                stack.push(p.right);
            }
 
            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
 
            p = p.right;
        }
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        
        flatten(root.left);
        flatten(root.right);
        
        if(root.left != null) {
            // Find the rightmost node
            TreeNode node = root.left;
            while(node.right != null) {
                node = node.right;
            }
            // rewire the connections
            node.right = root.right;
            root.right = root.left;
            root.left = null;
        }
    }
}

Solution 3

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        
        TreeNode node = root;
        
        while(node != null) {
            if(node.left != null) {
                // Find the rightmost node
                TreeNode rightmost = node.left;
                while(rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                // rewire the connections
                rightmost.right = node.right;
                node.right = node.left;
                node.left = null;
            }
            
            // move on to the right side of the tree
            node = node.right;
        }

    }
}

Follow up