Convert Binary Search Tree to Doubly Linked List - not working

Question

Solution i am pasting comes from this Geek URL

Its written in C, so i tried converting it in JAVA as below - (please do correct me if m wrong, i am not c/c++ person)

Program

   // A simple recursive function to convert a given Binary tree to Doubly
   // Linked List
   // root --> Root of Binary Tree
   // head --> Pointer to head node of created doubly linked list
   public void BinaryTree2DoubleLinkedList(BTNodes root, BTNodes head)
   {
           if(root == null)
               return;

           // Initialize previously visited node as NULL. This is
           // declared outside the recursive function so that the same value 
           // is accessible in all recursive calls   

            prev = null;

            // Recursively convert left subtree
            BinaryTree2DoubleLinkedList(root.getLeft(), head);

            //set head of LL if not set
            if(orgHead == null)
                orgHead = root;

            // Now convert this node
            if (prev == null)
                head = root;
            else
            {
                root.setLeft(prev);
                prev.setRight(root);
            }
            prev = root;

            // Finally convert right subtree
            BinaryTree2DoubleLinkedList(root.getRight(), head);
    }

Tree In Consideration

            10
          /   \
         5    15
        / \  /   \
       2  7 12   18
      /
     1
    /
   0

Problem

This program returns output :

0 1 2 5 7 10 15 18

As you can see, 12 is missing from the code.I tried to dry run it many times but still not able to find out the real issue.....I tried searching for different solutions but most of them traverse in the part-converted-LL which increases the time complexity.

Answer 1

In original C code function prototype is following:

void BinaryTree2DoubleLinkedList(node *root, node **head)

**head mean double pointer, head value can be changed within function using *head. In java you can't modify function parameter because they are always copied, but you can modify array element. So please try following code:

BTNode prev;

void BinaryTree2DoubleLinkedList(BTNodes root, BTNodes[] head)
{
    // Base case
    if (root == null) return;

    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all recursive
    // calls

    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(roor.getLeft(), head);

    // Now convert this node
    if (prev == null)
        head[0] = root;
    else
    {
        root.setLeft(prev);
        prev.setRight(root);
    }
    prev = root;

    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root.getRight(), head);
}

Initial call should look like:

BTNodes[] head = new BTNodes[1];
BinaryTree2DoubleLinkedList(root, head);
// result is in head[0]

To avoid ugly allocation for head element better to make additional function like following:

BTNodes BinaryTree2DoubleLinkedList(BTNodes root) {
    BTNodes[] head = new BTNodes[1];
    BinaryTree2DoubleLinkedList(root, head);
    return head[0];
}

Answer 2

Converting Binary Search tree into Doubly Linked List is kind of easy task if we use left and right fields of Node. Recursion helps us here.

• First, go down till the left node. Assign the left most leaf node as prev and also as head of list.
• Once control come back from leaf node to its parent, assign current node i.e. parent of left node as right of prev and left of current node as leaf node. Same is goes for right leaf child of current node.
• Once we are out of complete recursion, we will have our doubly linked list, with listHead and listTail.

{

Node prev = null;
Node listHead = null;
Node listTail = null;
public void convertToList(Node node)
{
    if(node == null)
        return;
    convertToList(node.left);
    if(listHead == null)
        listHead = node;
    if(prev == null)
        prev = node;
    else
    {
        node.left = prev;
        prev.right = node;
    }
    prev = node;
    convertToList(node.right);
    if(node.right == null)
        listTail = node;

}
public void printList()
{
    Node node = listHead;
    System.out.println("Doubly Linked List from Head: ");
    while(node!= null)
    {
        System.out.print(node.data+" ");
        node = node.right;
    }
}
public void printListFromTail()
{
    Node node = listTail;
    System.out.println("Doubly Linked List from Tail: ");
    while(node!= null)
    {
        System.out.print(node.data+" ");
        node = node.left;
    }
}

}

Answer 3

For any google visitor, i worked out a way to avoid head[0] - (this might pose problems if the program is called through different object for different trees, as head[0] may get overwritten)

Here is the implementation :

Trick is to remove prev = null; from the code and initialize tempHead = null and prev = null in the calling function, not in recursive call.

void BinaryTree2DoubleLinkedList(BTNodes root, BTNodes tempHead)
       {
           // Base case
           if (root == null) return; //optional, not needed in fact

           // Recursively convert left subtree
           if(root.getLeft() != null) //purely to reduce number of traversed node
               BinaryTree2DoubleLinkedList(root.getLeft(), tempHead);

          //set Original Head of the List, this would be leftmost
          //leaf in the tree
           if(orgHead == null) 
               orgHead = root;

           // Now convert this node
           if (prev == null)
               tempHead = root;
           else
           {
               root.setLeft(prev);
               prev.setRight(root);
           }
           prev = root;

           // Finally convert right subtree
           if(root.getRight() != null) //purely to reduce number of traversed node
               BinaryTree2DoubleLinkedList(root.getRight(), tempHead);
       }

Other helper Details :

Initial call :

BinaryTree2DoubleLinkedList(bst.root,tempHead); //root and null value

Traverse List

printList(orgHead); //pass original head to print function

Complexity :

Time = Space : O(n)

Answer 4

 public  void  ConverttoList(Node root){
    Node top = root;
    top.left = GetLeftNode(top.left);
    top.right = GetRightNode(top.right);
    top.left.right= top;
    top.right.left= top;
    Node leftmost = top.left;
    while(leftmost.left!=null){
        leftmost = leftmost.left;
    }
    while(leftmost!= null) {
        System.out.printf(leftmost.Data + "->");
        leftmost = leftmost.right;
    }

}

public Node GetLeftNode(Node root){
    if(root.left == null){
        return root;
    }
    else{
        Node startnode = GetLeftNode(root.left);
        startnode.right = root;
        root.left = startnode;
        root.right = GetRightNode(root.right);
        root.right.left = root;
        Node rightmost=root.right;
        while (rightmost.right!=null){
            rightmost=rightmost.right;
        }
        return rightmost;
    }
}

public  Node GetRightNode(Node root){
    if(root.left == null){
        return root;
    }
    else{
        Node startnode = GetLeftNode(root.left);
        startnode.right = root;
        root.left = startnode;
        root.right = GetRightNode(root.right);
        root.right.left = root;
        Node leftmost=root.left;
        while (leftmost.left!=null){
            leftmost=leftmost.left;
        }
        return leftmost;
    }
}

Answer 5

// bst to dll will generate a sorted dll
public class TreeToDLL {
    public static void main(String args[]){
        TreeNode t = new TreeNode(5);
        TreeNode t3 = new TreeNode(3);
        TreeNode t1 = new TreeNode(1);
        TreeNode t7 = new TreeNode(7);
        TreeNode t9 = new TreeNode(9);
        TreeNode t8 = new TreeNode(8);
        t.setLeft(t3);
        t3.setLeft(t1);
        t.setRight(t7);
        t7.setRight(t9);
        t9.setLeft(t8);
        DllNode dll = convert(t);
        dll.print();
    }
    static class DllNode{
        int data;
        DllNode next;
        DllNode prev;

        public DllNode(int data) {
            this.data = data;
        }
        public DllNode() {
        }
        public int getData() {
            return data;
        }
        public DllNode getPrev() {
            return prev;
        }
        public void setPrev(DllNode prev) {
            this.prev = prev;
        }

        public void setData(int data) {
            this.data = data;
        }
        public DllNode getNext() {
            return next;
        }
        public void setNext(DllNode next) {
            this.next = next;
        }
        public void print(){
            DllNode t = this;
            while(t!=null){
                System.out.print(t.getData()+"->");
                t = t.getNext();
            }
        }
    }
    static class TreeNode{
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public TreeNode getLeft() {
            return left;
        }

        public TreeNode setLeft(TreeNode left) {
            this.left = left;
            return this;
        }

        public TreeNode getRight() {
            return right;
        }

        public TreeNode setRight(TreeNode right) {
            this.right = right;
            return this;
        }
    }

    private static DllNode convert(TreeNode t){
        DllNode d =convert(t,new PreviousDLLNode());
        while(d.prev!=null){
            d = d.prev;
        }
        return d;
    }
    private static DllNode convert(TreeNode t, PreviousDLLNode d){
        if(t==null) return null;
        convert(t.getLeft(),d);
        DllNode dn = new DllNode(t.getData());
        if(d.val!=null){
            d.val.setNext(dn);
        }
        dn.setPrev(d.val);
        d.val = dn;
        convert(t.getRight(),d);
        return dn; // this node will be in the middle of the dll.
    }
    private static class PreviousDLLNode{
        DllNode val;
    }
}

Answer 6

I solved my problem inserting treenodes sorted in order in a DLL like that:

1. I added in my netBeans package the DoubleLinkedList and BinarySearchTree classes needed (including the TreeNode and the DoubleNode etc) and

2. I modified the BinarySearchTree as shown below:

       public class BinarySearchTree {
   
    DoubleLinkedList dL; 
   
   TreeNode root;
   
    public BinarySearchTree() {
   
   this.root = null;
       this.dL=new DoubleLinkedList(); 
   
   
     } 
       public void
   
       tree2DList(TreeNode TN) {
       if (TN == null) {
   
       return ;
   } else {
   
       tree2DList(TN.left);
       dL.insertLast((YourClassOfObjects)TN.getItem());
       tree2DList(TN.right);
   
   }
   return;
   }
   

I added a DoubleLinkedList field which I initialized in the default constructor of BST, calling the default constructor of DLL and I created the recursive method below, inspired from and following inOrderTraversal for the sorted input of tree nodes in the DLL