The solution given in the book is recursive so it uses space O(h), where h is the height of the tree. However this can be improved to O(1), when the nodes have a parent pointer. I offer such an implemention here.
9.13 Reconstruct binary tree from preorder traversal with markers - improved space complexity
lgtout
#1
0 Likes
hi @lgtout,
I am not sure this is Java or not, and I cannot understand this very well. Do you have a Java implementation?
0 Likes
lgtout
#3
@tsunghsienlee
It runs in the JVM 
. But no, it’s not Java . It’s Kotlin. Its more like Groovy (or Swift) than Java in syntax. I don’t have a Java language version.
0 Likes
It would be great if you can write this in languages I can understand otherwise I have no idea to verify the idea.
0 Likes
lgtout
#5
Valid point. Kotlin is primarily very popular among Android developers. So most people are unfamiliar with it.
0 Likes