'What is the space complexity of a recursive function that searches a BST? - O(h) or O(log(n))?
So I have written some code for a BST, where I am looking for whether a target node is contained in it.
At every recursive call, half of the tree gets 'eliminated', i.e. we reduce the number of nodes we need to search for in half. Now while I know this equates to O(log(n)) space, is it not also equivalent to the height of the tree O(h)?
As a visual example, please see below:
Say we are looking for 14 in our BST, the most number of recursive calls will be equal to the height of the tree, 3? Is this correct? And I imagine this extends to the general case too? As I can't think of an example where this would not be true.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|