2

I have implemented a Splay Tree class that uses nodes to store data. In this class I have tried to convert the data of nodes into a Singly Linked List. 1,000,000 nodes can be inserted into the splay tree and it works perfectly. Using recursion I get a StackOverFlow error when the tree contains 1,000,000 nodes. However when the tree contains around 15000 nodes it is able to be converted to a linked list without a problem.

Here is the code for my toList Method that is inside the splay tree class

public LinkedList<Node> toList() {

   LinkedList<Node> list = new LinkedList<Node>();
   Node node = root;
   addToList(node, list);

   return list;
}

private void addToList(Node node, LinkedList<Node> list) {
   if(node != null) {
      addToList(node.left, list);
      list.add(node);
      addToList(node.right, list);
   }
}

I used this test class below to test the function of this method

@Test
public void testConversionToLinkedList {
   SplayTree<Integer,String> st = new SplayTree<Integer,String>();
   for(int i = 0; i < 1000000; i++) {
      st.insert(i, Integer.toString(i));
   }
   assertEquals(1000000, st.size());

   LinkedList<Node> list = st.toList();
   assertEquals(1000000, list.size());
}

The test passes when the size entered is around 15000, however any number greater than that will show a StackOverFlowError

The error occurs at the line addToList(node.left, list);

This is really weird because when i used the same recursion technique to print the data of the nodes into a txt file, there is no StackOverFlow error and the data prints perfectly.

I have tried to use In Order Traversal, PreOrder and PostOrder but I still receive the same error at 1,000,000 nodes. I do know that it could be doing recursion too deeply and the stack runs out of memory. If that is the case is there any way I can convert a splay tree of nodes into a linked list? Any idea what could be going wrong? cheers

Yanzal
  • 103
  • 1
  • 7

2 Answers2

0

Your poblem is the recursive algorithm. As you figured out there is a limit in the stack size, which is build when you have recursion.

You can always transform recursion to a loop.

here are some examples for DFS and BFS algorithms using loops: Non recursive Depth first search algorithm

Sorontur
  • 480
  • 4
  • 15
0

You can increase the stack’s size. To do it you have to pass parameter to the jvm. The format is -Xss[g|G|m|M|k|K]. For example: java -Xss4m YourTreeProgram

niemar
  • 572
  • 1
  • 6
  • 16