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.

enter image description here

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);

So I understand from your tag you're getting a NPE? Can you post it with full stacktrace? — m0skit0, Feb 21 '14 at 16:55
possible duplicate of [What is a Null Pointer Exception?](http://stackoverflow.com/questions/218384/what-is-a-null-pointer-exception) — Brian Roach, Feb 21 '14 at 17:01
It's a logical error not NPE. Please stop downvoting. I am missing something in my logic that's why nodes are not connected properly, other wise right of head should not have been null, I Know what a NPE is, what I don't get is why right of head is null — java_doctor_101, Feb 21 '14 at 17:03
Did not check your code in detail. I would have made an in-order traversal of the tree and add nodes to the end of the list when I encounter them. — Henry, Feb 21 '14 at 17:10

score 2 · Answer 1 · answered Feb 21 '14 at 17:10

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.

answered Feb 21 '14 at 17:10

Radiodef

37,180
14
90
125

Hi, thanks I changed the code according to your answer and some other answers here. But now my code is not terminating, it's not going into second if condition, I am not able to figure out why. – java_doctor_101 Feb 21 '14 at 18:29

score 0 · Answer 2 · answered Feb 21 '14 at 17:25

0

As for your NullPointerException, I think that

          while(leftmost!=null)

should be

          while(leftmost.left!=null)

answered Feb 21 '14 at 17:25

Ray

4,829
4
28
55

score 0 · Accepted Answer · answered Feb 21 '14 at 17:27

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.

Converting Binary tree to Doubly linked list

3 Answers3