# Leetcode Count of Smaller Numbers After Self solution

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].

Solution is done using customized BST where count stores the total number of elements lesser than current element found from left to right.

class Solution:
def countSmaller(self, nums):
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.count = 0

def bst_insert(root, val, result, count):
if not root:
root = Node(val)
root.left = None
root.right = None
result.append(count)
return root
if val > root.val:
root.right = bst_insert(root.right, val, result, root.count + 1 + count)
else:
root.count += 1
root.left = bst_insert(root.left, val, result, count)
return root

root = None
result = []
for num in nums[::-1]:
if not root:
root = Node(num)
result.append(0)
else:
bst_insert(root, num, result, 0)
return result[::-1]

• What is a "BST"? – ben rudgers Dec 17 '17 at 13:55
• @benrudgers Binary Search Tree. – Mast Dec 17 '17 at 21:09

Next, your bst_insert has redundant code. root.left = None and root.right = None are already done in your constructor, so you don't need to duplicate them.
The last piece of advice is to use reversed(nums) instead of num[::-1] as the former does not make a copy, which should be faster and use less memory.