convert a binary search tree to a linkedlist in JAVA

Question

 public static BiNode linklist(BiNode root)
 {
    BiNode head = null, tail=null;
    convertBST(head, tail, root);
    return head;
 }



 public static void convertBST(BiNode head, BiNode tail, BiNode root)
 {
    BiNode leftTail = null, rightHead = null;
    if(root==null){
        head = null;
        tail = null;
        return;
    }
    System.out.println("root = "+root.key);
    convertBST(head, leftTail, root.node1);
    convertBST(rightHead, tail, root.node2);
    if(leftTail != null)
    {
        System.out.println("leftTail = "+leftTail.key);
        leftTail.node2 = root;
        root.node1 = leftTail;
    }else{
        head = root;
        System.out.println("head = "+ head.key+", root = "+root.key);
    }

       if(rightHead != null)
       {
        rightHead.node1 = root;
        root.node2 = rightHead;
       }else{
        tail = root;
        System.out.println("tail = "+ tail.key+", root = "+root.key);
       }
  }

above is my java code which is used to convert a BST to a double link list.

But I do not know why the head always change, which is supposed to point to the head of the link list and not change.

I am glad great mind would help me debug this code! thanks!!!

Could you just post the code for linklist() and convertBST()? None of the other code appears to contribute to your BST to linked list logic, so it just clutters everything up. It'll also help a bit if everything is indented neatly. — Dennis Meng
– Dennis Meng, Commented Jul 2, 2013 at 17:26

John B · Accepted Answer · 2013-07-02 17:38:09Z

1

The basic key as to why the code is wrong is this line: head = root; and tail = root; in the method public static void convertBST(BiNode head, BiNode tail, BiNode root)

You are assuming that when you set a parameter to a new node it is propagated up the call stack (call by reference). Java does not do this. When you do head = root; you have only changed the local value of head not the value in the calling method.

Therefore in the method public static BiNode linklist(BiNode root){, head will always be null and the method will always return null.

answered Jul 2, 2013 at 17:38

John B

33.1k8 gold badges80 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

city Over a year ago

I get it. But how to fix it? I know how to fix this kind problem in c/c++, but how to fix it in JAVA? thank you again

John B Over a year ago

Either return the value(s) or pass in a mutable wrapper of the values

Collectives™ on Stack Overflow

convert a binary search tree to a linkedlist in JAVA

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related