Binary Search Tree to Doubly Linked List

Question

I'm creating a Doubly Linked List from a Binary Search Tree using recursion and it works perfectly fine when the BST is already populated, i.e. >=2 nodes. However, I tried running it for a BST that is dynamically getting populated and it gives me a StackOverFlowError as soon as I insert a child to the root node in the BST. Here is the code (in Java) I've written

public class BSTtoDLL {
/* Binary Search Tree to Doubly Linked List conversion*/

     // head --> Pointer to head node of created doubly linked list
     static BTNode head;

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

    /* BSTtoDLL Construtor */
    public BSTtoDLL(){
        head = null;
        prev = null;
    }

     // A simple recursive function to convert a given Binary tree 
     // to Doubly Linked List
     // root --> Root of Binary Tree
     void BinaryTree2DoubleLinkedList(BTNode root)
     {
         // Base case
         if (root == null)
             return;

         // Recursively convert left subtree
         if(root.left!=null)
            BinaryTree2DoubleLinkedList(root.left);

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

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

And the the console response:

Binary Tree Test
Converting to a DLL
Data--34--Left is Null----Right is Null---
Binary Tree Test Converting to a DLL Exception in thread "main" java.lang.StackOverflowError
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)
at com.techwealth.BSTtoDLL.BinaryTree2DoubleLinkedList(BSTtoDLL.java:32)

score 1 · Accepted Answer · edited May 23 '17 at 12:32

1

Clearly, you are missing the termination condition(the base case is invalidated as you are using static variables). That is the reason why you are seeing stackoverflow error. Go through this link for more info regarding this error: What is a StackOverflowError?

edited May 23 '17 at 12:32

Community

1
1

answered Jul 24 '16 at 05:26

Prashanth Peddabbu

92
1
1
11

Binary Search Tree to Doubly Linked List

1 Answers1