Flatten Binary Tree to Linked List. Time Complexity : O(n). Don't use extral space.

FlattenBinaryTreeToLinkedList.java

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode(int val){
        this.val = val;
    }
}

public void flatten(TreeNode root){
    root = flatten(root, null);
}
// Recurisve version
TreeNode flatten(TreeNode cur, TreeNode next){
    if (cur == null) return next;
    next = flatten(cur.right, next);
    next = flatten(cur.left, next);
    cur.right = next;
    cur.left = null;
    return cur;
}
// Iterative version
public static void flattenIterative(TreeNode root){
    if (root == null) return;
	Stack<TreeNode> stack = new Stack<TreeNode>();
	stack.push(root);
	TreeNode prev = null;
	while (!stack.isEmpty()){
		TreeNode ptr = stack.pop();
		if (ptr.right != null)
			stack.push(ptr.right);
		if (ptr.left != null)
			stack.push(ptr.left);
		if (prev != null){
			prev.right = ptr;
			prev.left = null;
		}
		prev = ptr; 
	}
}