Search code examples
pythonbinary-search-treespace-complexity

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:

enter image description here

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.

Solution

  • In BSTs h corresponds to log(n) only when the tree is perfectly balanced, while in general your search will be O(h).

    Take for example the case of a tree completely skewed to one side, like this: chain bst tree

    The tree's height here is 7 and the worst case is where will you be searching the last node, performing 7 steps into the tree, so not a log(n) complexity.