Doubt about computing running time / time complexity of a function in Python

Question

I am learning about time complexity now, and I am working with BST (Binary Search Trees).

This question needs some context and this is a follow up post to this post. Basically, I would like to compute the time complexity of the function below. The function below refers to a BinarySearchTree where 'u.l' represents the left child of 'u' and 'u.r' represents the right child of 'u'. Additionaly, 'u.p' represents the parent of 'u' and 'self.r' represents the root of our binary search tree.

def remove_node(self,u):                                
    if u.r == None or u.l == None: self.splice(u)       
    else:                                               
        w = u.r                                         
        while w.l != None:                              
            w = w.l
    u.x = w.x                                           
    self.splice(w)                                      

In the post I linked, we showed that splice(self,u) is a function with O(1) time-complexity and thus every statement that uses this function only will also have O(1) time complexity. Being aware of this, the best case scenario will be obviously when we enter the first if statement and in this case we will have that remove_node function is O(1) time-complexity (since u.x = w.x and self.splice(w) are also O(1) procedures).

With this being said, we must now study the worst case scenario, which is when we enter the else statement instead of the if statement. w = u.r is an atributtion and so it is O(1) in time complexity.

And now is where my trouble begins. The main question here is: How many times will be while cycle run? Well, this one is obvious. It will run as much times as the number of nodes in the left path of u.r to the end of the tree. But how would one translate this into time-complexity? Because we might have a BST such that u.r == None and thus the while cycle will run 0 times, but we might also have a BST such that u.r != None and in this case the while cycle will run a total of ntimes, where n represents the number of nodes to the left of u.r and its left descendants.

Below I give two examples of how many times the while cycle would run in this scenarios:

          u      
            \ 
             u.r
              /
           u.r.l                   => The while cycle will run 4 times
          /    \
     u.r.l.l   u.r.l.r
     /
u.r.l.l.l

But there are other examples. How would one determine the time complexity of this function? Thanks for any help in advance!

Answer 1

You could say that this function has a time complexity of $\mathcal{O}(h)$, where $h$ is the height of the BST.

You could be more precise and say that it is a $\Theta(h)$ in the worst case. This means that the complexity will never be more than linear in the height, but adds that this linear case can be reached (even if not every time as you have stated).

Answer 2

While Nathaniel's answer is obviously right, there is something else to consider: Do the operations that you perform change the shape of your tree? I binary tree with 1000 nodes could have a height of 10, or it could be degenerated to a linked list with a height of 1,000. That would happen if you have a naive implementation of "add a node" and add 1,000 nodes in sorted order.

So what is the height of your average tree, based on the algorithms that you are using?