Binary Search Tree inorder predecessor space complexity

Question

I am studying binary search trees and have not been able to find much information on the space required to find the predecessor of a given node. Bases on an iterative approach, I believe I would need O(1) space (in-place) because we only need one variable plus a single node on a stack. To accomplish this recursively, we would have to maintain a stack. Since it is possible to traverse to the left most/minimum node, it is possible that we would traverse the entire height of the binary search tree. Therefore, the space complexity for this would be O(h).

Are these assumptions correct or am I missing anything?

Answer 1

Keep in mind that each recursive call decreases the height, and there is only a single call for each height value. Therefore, we can perform an iterartive search.

Let n1, n2 be nodes such that n2 is the root and n1 is null. Let v be the node you are looking for

While n2 is not v:

• n1 := n2
• if v.value > n2.value, n2 := n2.right
• else n2 := n.left

return n1

I've kept a constant number (2) of pointers, therefore the complexity is O(1).