Your BST can become unbalanced. In the worst case when the input is sorted, the tree degenerates to a linked list, and you traverse through it all to insert each element. Various algorithms exist for self-balancing search trees, but you might also want to look into the SortedContainers library.

Your BST can become unbalanced. In the worst case when the input is sorted, the tree degenerates to a linked list, and you traverse through it all to insert each element. Various algorithms exist for self-balancing search trees, but you might also want to look into the SortedContainers library. Even if you want to create your solution from scratch, you can find good ideas there.

Using sortedcontainers.SortedList the solution becomes very simple:

def countSmaller(self, nums):
    result = []
    seen = sortedcontainers.SortedList()
    for num in reversed(nums):
        result.append(seen.bisect_left(num))
        seen.add(num)
    result.reverse()
    return result

This is twice as fast as yours for 300 random numbers, and the gap increases as the size grows. For list(range(100)) this is ten times as fast.