0

I am working on an algorithm problem. I need to traverse a tree with 30000 nodes in pre-order.

With my experiments, I found when the recursion level is bigger than 10000, it will result in stack overflow. We know non-recursion version of pre-order traversing of a general tree is not that easy to implement, so I am trying to make the stack size bigger.

Since it is an online judge, I can't configure the stack size directly. I know there is a way to write some #prgram instructions in C++ to change the stack size, so I want to if there exists something similar to that in Scala.

ctzsm
  • 3
  • 1
  • "We know non-recursion version of pre-order traversing of a general tree is not that easy to implement,". It's not that difficult, either. Probably easier than trying to change the stack size dynamically! Instead of recursing, push the current node (and index of how far you are through the children, if more than two) onto a stack, move to the next child, etc, When you're processed a leaf, pop the previous node/position from the stack – The Archetypal Paul Jun 20 '14 at 21:50

3 Answers3

1

If it's scala it's almost certainly running on some sort of JVM. The stack size is one of the properties of JVM that remains constant during it's lifetime. So I guess you're out of luck using just recursion.

Have a look at: programatically setting max java heap size

If it's tail recursive you could convert it to an iteration, but I guess you'd know that already.

Community
  • 1
  • 1
aa333
  • 2,556
  • 16
  • 23
0

I don't know if you can do that but... Have you hear about tail recursion? It is a way to improve recursive functions and scala has this feature.

Look at this video from the creator of scala and see if you can do your a similar way (at least for the last call since you need 2 calls per node).

nightshade
  • 638
  • 5
  • 15
  • Sure, I know tail recursion, but that is impossible in my case since a node may have more than one child, and I have finished this course last year, thank you! – ctzsm Jun 20 '14 at 20:53
0

No, there isn't a way to do that in Scala, but note that for a tree traversal, it's not the number of nodes, but the depth of the tree that's important. In other words, the distance from the root to the farthest leaf. These are the only nodes being held in the stack at any given time. For a 30,000 node balanced binary tree, that depth is 15. It takes quite a bit of imbalance to get anywhere close to a depth of 10,000.

Karl Bielefeldt
  • 47,314
  • 10
  • 60
  • 94
  • You are correct, but since this is an algorithm problem, we could have a test case which has a very long chain. Thanks! – ctzsm Jun 20 '14 at 21:37