Converting Binary tree to Doubly linked list

Question

I am trying to write a function in java to convert a binary tree to DLL. The function executes without error but the DLL is not being made. Following is the function. root is pointer to the root of the tree and head points to the starting node of the DLL.

public void dll(Node x)
    {

        if(x==null)
        {
            return;
        }
        else
        {
            if(x==root)
            {
                Node temp=root;
                while(temp.left!=null)
                {
                    temp=temp.left;
                }
                head=temp;
            }

            if(x.left!=null)
            {
                System.out.println(x.data);

                Node lchild=x.left;
                Node rightmost=lchild;
                while(rightmost.right!=null)
                {
                    rightmost=rightmost.right;
                }
                x.left=rightmost;
                rightmost.right=x;
                dll(lchild);

            }
            if(x.right!=null)
            {
                System.out.println(x.data);

                Node rchild=x.right;
                Node leftmost=rchild;

                while(leftmost.left!=null)
                {
                    leftmost=leftmost.left;
                }

                x.right=leftmost;
                leftmost.left=x;
                dll(rchild);
            }




        }

    }
}

The logic is as follows: Find the rightmost in left subtree and make is previous node of root and find leftmost in right sub tree and make it next of the root. Recursive apply for subtrees.

When I try to print head.right, it gives me Null pointer exception.

Exception in thread "main" java.lang.NullPointerException
        at BTtoDll.main(BTtoDll.java:153)

Line 153 is -

 System.out.println(t.head.right.data);

Answer 1

The pure recursive function in fact does the same: the right-most of the left subtree connected to x and x connected to the left-most of the right subtree. I thought you might be interested to see the congruity.

public DLL dll(Node x) {
    return dll(null, x, null);
}

public DLL dll(DLL before, Node x, DDL after) {
    if (x == null) {
        return;
    }
    if (x.left != null) {
        before = dll(before, x.left, null);
    }
    if (x.right != null) {
        after = dll(null, x.left, after);
    }
    DLL result = new DLL();
    result.insert(x.value);
    result.insertBefore(before); // null being a no-op.
    result.insertAfter(after); // null being a no-op.
    return result;
}

As one can see, there are several variations thinkable.

Answer 2

Here you assign x.left and x.right to x:

if(x.left!=null)
{
    ...
    rightmost=x;
    x.left=rightmost;
    ...
}
if(x.right!=null)
{
    ...
    leftmost=x;
    x.right=leftmost;
    ...
}

I can't tell what it's supposed to be to say what to change it to but that's probably your bug. The list won't be relinked.

Answer 3

As for your NullPointerException, I think that

          while(leftmost!=null)

should be

          while(leftmost.left!=null)