Count Of Smaller Numbers After Self is an example of tree problems. In this post we will see how we can solve in Javascript.

Problem 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:

Input: [5,2,6,1]
Output: [2,1,1,0]

Explanation:

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

Our insert method

  • To insert a node into the BST root at the same time as outputing into count Arr how many smaller nodes were inserted before the current root node.
  • When root is null, create a new Node using val and count and insert count into countArr at index position.
  • When the value of root is greater than val, increment the root count and insert val into the left node of root.
  • When the value of root is smaller or equal to val, insert val into the right node of root incrementing count by one only if the root value is smaller than val.

Complete Implementation: Please check the main.js snippet for the solution.  If you have different approach in mind or have any suggestion for this implementation feel free to share in the comment below. Thanks!