The standard sorted array code is to start from both ends and move two pointers in tandem based on whether their sum is greater than, or lesser than K.
In the case of BST though, keeping the pointers to the nodes will mean storing the recursion stack as well. That's log(n) storage. Is that acceptable?
Or is there a "pure" constant space solution that doesn't even take the recursion stack depth into account?
The standard sorted array code is to start from both ends and move two pointers in tandem based on whether their sum is greater than, or lesser than K.
ReplyDeleteIn the case of BST though, keeping the pointers to the nodes will mean storing the recursion stack as well. That's log(n) storage. Is that acceptable?
Or is there a "pure" constant space solution that doesn't even take the recursion stack depth into account?