Counting smaller elements on the right side

Optimal Approach Using Self Balancing Bst

1. We will use self-balancing bst to solve this problem in O(N(log(n)) time. 
2. We will traverse the array from left to right and insert these elements into the tree.
3. While inserting the new key, we will first compare the new key with the root. If the key is greater than the root, it would be greater than all the nodes of the left subtree of the root. 
4. So we will add the size of the left subtree to the count of smaller elements for the key being inserted. 
5. We will recursively follow this process for all the nodes of the tree.

Implementation in C++

// C++ code for counting smaller elements on the right side
#include <bits/stdc++.h>
using namespace std;

// AVL tree node
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;

    // to store the size of tree
    int size;
};

// function to get the hieght of the tree
int height(struct node *N)
{
    if (N == NULL)
        return 0;

    return N->height;
}

// function to get the size of the tree
int size(struct node *N)
{
    if (N == NULL)
        return 0;

    return N->size;
}

// function to get max of two numbers
int max(int a, int b)
{
    return (a > b) ? a : b;
}

// function create a new node in the tree
struct node *newNode(int key)
{
    struct node *node = (struct node *)
        malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;

    // initially the new node
    // is added on leaf
    node->height = 1;
    node->size = 1;
    return (node);
}

// function to right rotate the subtree rooted with r
struct node *rightRotate(struct node *r)
{
    struct node *x = r->left;
    struct node *y = x->right;

    // perform the rotation
    x->right = r;
    r->left = y;

    // update the heights
    r->height = max(height(r->left), height(r->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // update the size
    r->size = size(r->left) + size(r->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;

    // return the root
    return x;
}

// function to right rotate the subtree rooted with r
struct node *leftRotate(struct node *r)
{
    struct node *x = r->right;
    struct node *y = x->left;

    // perform the rotation
    x->left = r;
    r->right = y;

    // update the heights
    r->height = max(height(r->left), height(r->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // update the size
    r->size = size(r->left) + size(r->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;

    // return the root
    return x;
}

// function to get the balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
        return 0;

    return height(N->left) - height(N->right);
}

// function to insert a new key in the tree rooted with the node
// also updates the count of smaller elements for the new key
struct node *insert(struct node *node, int key, int *count)
{
    // 1. First perform the normal rotation
    if (node == NULL)
        return (newNode(key));

    if (key < node->key)
        node->left = insert(node->left, key, count);
    else
    {
        node->right = insert(node->right, key, count);

        // to update the count of smaller elments for the key
        *count = *count + size(node->left) + 1;
    }

    // 2. Now, update the hieght and size of the ancestor node
    node->height = max(height(node->left), height(node->right)) + 1;
    node->size = size(node->left) + size(node->right) + 1;

    // 3. After that, get the balance factor of the ancestor node
    int balance = getBalance(node);

    // if the node becomes unbalanced then,

    // left left case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // right right case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // left right case
    if (balance > 1 && key > node->left->key)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // right left case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

// function to update the countSmaller[] array
void constructLowerArray(int arr[], int countSmaller[], int n)
{
    struct node *root = NULL;

    for (int i = 0; i < n; i++)
        countSmaller[i] = 0;

    // start from the rightmost element, and then insert
    // all the elments one by one in the AVL tree and
    // then get the count of the smaller elements
    for (int i = n - 1; i >= 0; i--)
    {
        root = insert(root, arr[i], &countSmaller[i]);
    }
}

// function the print the array
void printArray(int arr[], int size)
{
    cout << endl;

    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
}

// Driver code
int main()
{
    int arr[] = {5, 3, 6, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    int *l = (int *)malloc(sizeof(int) * n);

    constructLowerArray(arr, l, n);

    printArray(l, n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Input: arr[] = {5, 3, 6, 1, 9}  
Output: 2 1 1 0 0 

Complexity Analysis

Time Complexity: O(N(log(N))

Insertion of N elements in bst causes O(N(log(N)) time complexity.

Space Complexity: O(N)

Creation of bst of size N takes O(N) time.

Optimal Approach Using BST with two extra fields

1.  Binary Search Tree which will have two extra fields:
2. One field will hold the elements on the left side of the node, and the second field will store the frequency of elements.
3. We will traverse the array from right to left and insert these elements into the tree.
4. While inserting the new key, we will compute the number of lesser elements than the current ones. We will do this by simply computing the sum of the frequencies of the elements and the number of elements to the left side of the current node.
5. Once we place an element to its correct position, we can its sum value. 
6. We will recursively follow this process for all the nodes of the tree.

Implementation in C++

// C++ code for counting smaller elements on the right side
#include <bits/stdc++.h>
using namespace std;

// BST node structure
struct Node
{
    int val, count;
    Node *left, *right;

    // Constructor
    Node(int num1, int num2)
    {
        this->left = this->right = NULL;
        this->count = num2;
        this->val = num1;
    }
};

// function to add a node
int addNode(Node *&root, int countSmaller, int value)
{

    // base case
    if (root == NULL)
    {
        root = new Node(value, 0);
        return countSmaller;
    }
    if (root->val < value)
    {
        return root->count + addNode(root->right, countSmaller + 1, value);
    }
    else
    {
        root->count++;
        return addNode(root->left, countSmaller, value);
    }
}

// Driver code
int main()
{
    int arr[] = {6, 1, 4, 9, 5, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans[n] = {};

    Node *root = NULL;

    for (int i = n - 1; i >= 0; i--)
        ans[i] = addNode(root, 0, arr[i]);

    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Input: arr[] = {6, 1, 4, 9, 5, 7}  
Output: 3 0 0 2 0 0  

Complexity Analysis

Time Complexity: O(N(log(N))

Insertion of N elements in bst causes O(N(log(N)) time complexity.

Space Complexity: O(N)

Creation of bst of size N takes O(N) time.

Check out this problem - Next Smaller Element

FAQs

1. What is the searching time complexity in a BST?
   On average, the worst-case time complexity is O(Logn), and in the worst case, it’s O(n), i.e., the case of a skewed BST where ‘n’ is the number of nodes in the BST.  
    
2. What are leave nodes in a binary tree?
   Leave nodes of a tree are those nodes that don’t have any children, and both the pointers of the nodes point to null.
    
3. What is level order traversal?
   A traversal that always travels depending on the tree's level is known as a Level Order Traversal. From the root node, this traversal initially visits the nodes corresponding to Level 0, then Level 1, and so on.

Key takeaways

This article discussed the problem of counting smaller elements on the right side. We have discussed three approaches to this problem: the brute force approach, the second one is an optimal approach using self-balancing bst, and the last one is also optimal, but it uses bst with two extra fields. We have also discussed the time complexities of all the approaches.

You can try these additional problems:

1. Insert a node in BST
2. Search a node in BST
3. BST from preorder
4. Maximum Sum Path In BST

Until then, Keep Learning and Keep Coding.