Spatial complexity of checking binary search tree

Question

The best algorithm for checking if a BST binary tree is as follows

IsValidBST(root,-infinity,infinity); bool IsValidBST(BinaryNode node, int MIN, int MAX) { if(node == null) return true; if(node.element > MIN && node.element < MAX && IsValidBST(node.left,MIN,node.element) && IsValidBST(node.right,node.element,MAX)) return true; else return false; } 

The spatial complexity of this logic, apparently O(logN) , which I assume is the cost of recursion. How was the value reached?

Answer 1

My comment has been updated to respond:

There is no additional data except method variables and return value, so really, all memory is the "recursion cost". Thus, the total cost will be linearly proportional to the depth of the tree.

In a balanced binary search tree, the depth is O(log n) , so the complexity of the space will also be O(log n) . However, generally speaking, BST is not necessarily balanced, it can even be a chain of length n, if the root is a minimum, its right child is the second smallest element, etc. In this case, the spatial complexity of this recursion is O(n) .