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.

CodePudding user response：

In BSTs h corresponds to log(n) only when the tree is perfectly balanced (often not the case), so in general your search will be O(h)