Count of Smaller Numbers After Self This is a LeetCode.com problem. 
https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/


  You are given an integer array nums and you have to return a new
  counts array. The counts array has the property where counts[i] is the
  number of smaller elements to the right of nums[i].
  
  Example:
  
  Given nums = [5, 2, 6, 1]
  
  To the right of 5 there are 2 smaller elements (2 and 1). To the right
  of 2 there is only 1 smaller element (1). To the right of 6 there is 1
  smaller element (1). To the right of 1 there is 0 smaller element.
  
  Return the array [2, 1, 1, 0].


Following is my solution which is accepted. But I noticed my run time is lot higher than many other submissions. I am curious to know if there is a better algorithm to this problem or is it something in the implementation that I can improve? How pythonic is my code? Do you see issues with any logic that could be done in a better way (both performance and code beauty wise)

Algorithm:
I start traversing the input list from the end. I take each element and insert it into a BST. While inserting I also track for each node in the BST, how many nodes are left of it (the size of left subtree) which denotes elements that are strictly smaller than current node. I also compute a position variable that starts at zero at root and gets incremented by X, each time a node is visited with value less than the given node where X is the count of its left subtree size plus one. If the number is equal, I only increment it by the node's left subtree count.

class bst_node(object):

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.left_count = 0 # less than

# Name of this class is given by LeetCode, not my choice.
class Solution(object):

    def add_node(self, bst_pointer, new_node, position):
        if bst_pointer == None:
            return position, new_node
        if new_node.val &lt; bst_pointer.val:
            bst_pointer.left_count += 1            
            position, bst_pointer.left = self.add_node(bst_pointer.left, new_node, position)
        else:
            if new_node.val &gt; bst_pointer.val:
                position += 1
            position += bst_pointer.left_count 
            position, bst_pointer.right = self.add_node(bst_pointer.right, new_node, position)
        return position, bst_pointer

    # This method signature is also given by Leetcode.
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        bst = None

        for n in nums[::-1]:
            smaller_after, bst = self.add_node(bst, bst_node(n), 0)
            res.append(smaller_after)

        return res[::-1]

# Few test cases ...
print(Solution().countSmaller([]))    
print(Solution().countSmaller([5, 2, 6, 1]))
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.