Flatten Binary Tree to Linked List | LeetCode | Java

#leetcode #java #algorithms #beginners

Approach 1 : Using DFS

class Solution {
    TreeNode prevNode = null;
    public void flatten(TreeNode root) {

        if(root==null)
            return;

        flatten(root.right);
        flatten(root.left);
        root.right = prevNode;
        root.left = null;
        prevNode = root;
    }
}

Approach 2 : Using Stack (BFS)

class Solution {
    public void flatten(TreeNode root) {

        if(root==null)
            return;

        Stack<TreeNode> stack = new Stack<>();

        stack.add(root);

        while(!stack.isEmpty()){

                TreeNode currentNode = stack.pop();

                if(currentNode.right!=null)
                    stack.push(currentNode.right);

                if(currentNode.left!=null)
                    stack.push(currentNode.left);

                if(!stack.isEmpty())
                    currentNode.right = stack.peek();

                currentNode.left = null;
        }
    }
}