Convert a BST into preorder and postorder linkedlists

Question

This is a round-2 Amazon interview question.Convert a given Binary Search Tree into pre-order and post-order linked lists and this conversion has to be inplace.

Answer 1

Below code is written to do flattening of Binary Tree in pre-Order traversal form without using stack. It uses pre-Order traversal recursive approach. In this, TreeNode[] arr will hold the last most left node value on which I am updating right pointer of that node.

    public TreeNode preorderNode(TreeNode root,TreeNode[] arr)
    {
    if(root==null)
        return null;
    if(root!=null && root.left==null && root.right==null)    
        {
            arr[0]=root;
            return root;
        }
    TreeNode temp=root.right;
    if(root.left!=null)
        root.right=preorderNode(root.left,arr);
    else arr[0]=root;
    root.left=null;
    arr[0].right=preorderNode(temp,arr);
    return root;
    }
    public void flatten(TreeNode root) {

        if(root==null || (root.left==null && root.right==null))
            return;
        TreeNode temp=root.right;    
        TreeNode[] arr=new TreeNode[1];
        arr[0]=null;
        if(root.left!= null)
            root.right=preorderNode(root.left,arr);
        else
            arr[0]=root;
        root.left=null;
       arr[0].right=preorderNode(temp,arr);
   }