2 ms·
> Your limit is only for fully balanced trees. On a fully unbalanced tree your solution will crash at about 100 elements. 5E29 assumes not-quite-balanced. Yes
by mlyle 6y ago
> Your limit is only for fully balanced trees. On a fully unbalanced tree your solution will crash at about 100 elements.
5E29 assumes not-quite-balanced. Yes, I'm assuming some kind of balanced binary tree data structure, not other things that are tree-like. There are some things that are much better than 5E29, like btrees. :P
If you have really deep unbalanced trees, you may want to have a smaller stack frame and/or pay the pain of doing things iteratively with your own stack. (Or have upward links in your tree and do it purely iteratively but slow).
> The compiler cannot elide away tree traversal with tail-call optimisation. Only one branch.
Yah, sorry. Just for search, not for full traversal.