Count smaller elements on right side using binary search tree

Here given code implementation process.

/*
    C program for
    Count smaller elements on right side using binary search tree
*/
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
	int data;
	int count;
	struct TreeNode *left;
	struct TreeNode *right;
};
// Binary Search Tree
struct BinarySearchTree
{
	struct TreeNode *root;
};
// Create new tree
struct BinarySearchTree *newTree()
{
	// Create dynamic node
	struct BinarySearchTree *tree = (struct BinarySearchTree *)
	malloc(sizeof(struct BinarySearchTree));
  
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	// Return new tree
	return tree;
}
// This is creates and returns the new binary search tree node
struct TreeNode *getNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *)
	malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
		// number of left child 
		node->count = 0;
	}
	else
	{
		// This is indicates, segmentation fault or 
      	// memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
// Adding a new node in binary search tree and
// Returns the number of an element smaller than the given data
int smallerElement(struct BinarySearchTree *tree, int data)
{
	struct TreeNode *node = getNode(data);
	if (node != NULL)
	{
		if (tree->root == NULL)
		{
			tree->root = node;
		}
		else
		{
			struct TreeNode *auxiliary = tree->root;
			int count = 0;
			// Add new node in binary search tree
			while (auxiliary != NULL)
			{
				if (data >= auxiliary->data)
				{
					// Update result counter
					if (auxiliary->data == data)
					{
						// When node are same
						count += auxiliary->count;
					}
					else
					{
						count += auxiliary->count + 1;
					}
					if (auxiliary->right == NULL)
					{
						// Add new node at right child
						auxiliary->right = node;
						return count;
					}
					auxiliary = auxiliary->right;
				}
				else
				{
					// Incress number of left child
					auxiliary->count += 1;
					if (auxiliary->left == NULL)
					{
						// Add new node at left child
						auxiliary->left = node;
						return count;
					}
					auxiliary = auxiliary->left;
				}
			}
		}
	}
	return 0;
}
// Display given array elements
void printRecord(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
}
int main()
{
	struct BinarySearchTree *tree = newTree();
	int arr[] = {
		6 , 2 , 1 , 0 , 2 , 7 , 4 , 0 , 1 , 7 , 3 , 9 , 8
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	int result[n];
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	for (int i = n - 1; i >= 0; --i)
	{
		result[i] = smallerElement(tree, arr[i]);
	}
	printf("\n Array  : ");
	printRecord(arr, n);
	printf("\n Result : ");
	printRecord(result, n);
	return 0;
}

Output

 Array  :   6  2  1  0  2  7  4  0  1  7  3  9  8
 Result :   8  4  2  0  2  4  3  0  0  1  0  1  0
/*
    Java Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public TreeNode left;
	public TreeNode right;
	public int count;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
		this.count = 0;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	public int smallerElement(int data)
	{
		TreeNode node = new TreeNode(data);
		if (node != null)
		{
			if (this.root == null)
			{
				this.root = node;
			}
			else
			{
				TreeNode auxiliary = this.root;
				int count = 0;
				// Add new node in binary search tree
				while (auxiliary != null)
				{
					if (data >= auxiliary.data)
					{
						// Update result counter
						if (auxiliary.data == data)
						{
							// When node are same
							count += auxiliary.count;
						}
						else
						{
							count += auxiliary.count + 1;
						}
						if (auxiliary.right == null)
						{
							// Add new node at right child
							auxiliary.right = node;
							return count;
						}
						auxiliary = auxiliary.right;
					}
					else
					{
						// Incress number of left child
						auxiliary.count += 1;
						if (auxiliary.left == null)
						{
							// Add new node at left child
							auxiliary.left = node;
							return count;
						}
						auxiliary = auxiliary.left;
					}
				}
			}
		}
		return 0;
	}
	// Display given array elements
	public void printRecord(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public static void main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		int[] arr = {
			6 , 2 , 1 , 0 , 2 , 7 , 4 , 0 , 1 , 7 , 3 , 9 , 8
		};
		// Get the number of elements
		int n = arr.length;
		int[] result = new int[n];
		// Inserting the node in binary search tree and
		// Count number of smaller element in right side
		for (int i = n - 1; i >= 0; --i)
		{
			result[i] = tree.smallerElement(arr[i]);
		}
		System.out.print("\n Array  : ");
		tree.printRecord(arr, n);
		System.out.print("\n Result : ");
		tree.printRecord(result, n);
	}
}

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode
{
	public:
	// Data value 
	int data;
	// Indicates left and right subtree
	TreeNode *left;
	TreeNode *right;
	int count;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
		this->count = 0;
	}
};
class BinarySearchTree
{
	public: TreeNode *root;
	BinarySearchTree()
	{
		this->root = NULL;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	int smallerElement(int data)
	{
		TreeNode *node = new TreeNode(data);
		if (node != NULL)
		{
			if (this->root == NULL)
			{
				this->root = node;
			}
			else
			{
				TreeNode *auxiliary = this->root;
				int count = 0;
				// Add new node in binary search tree
				while (auxiliary != NULL)
				{
					if (data >= auxiliary->data)
					{
						// Update result counter
						if (auxiliary->data == data)
						{
							// When node are same
							count += auxiliary->count;
						}
						else
						{
							count += auxiliary->count + 1;
						}
						if (auxiliary->right == NULL)
						{
							// Add new node at right child
							auxiliary->right = node;
							return count;
						}
						auxiliary = auxiliary->right;
					}
					else
					{
						// Incress number of left child
						auxiliary->count += 1;
						if (auxiliary->left == NULL)
						{
							// Add new node at left child
							auxiliary->left = node;
							return count;
						}
						auxiliary = auxiliary->left;
					}
				}
			}
		}
		return 0;
	}
	// Display given array elements
	void printRecord(int arr[], int n)
	{
		for (int i = 0; i < n; ++i)
		{
			cout << " " << arr[i];
		}
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	int arr[] = {
		6 , 2 , 1 , 0 , 2 , 7 , 4 , 0 , 1 , 7 , 3 , 9 , 8
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	int result[n];
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	for (int i = n - 1; i >= 0; --i)
	{
		result[i] = tree->smallerElement(arr[i]);
	}
	cout << "\n Array  : ";
	tree->printRecord(arr, n);
	cout << "\n Result : ";
	tree->printRecord(result, n);
	return 0;
}

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
// Include namespace system
using System;
/*
    Csharp Program for
    Count smaller elements on right side using binary search tree
*/
public class TreeNode
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public TreeNode left;
	public TreeNode right;
	public int count;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
		this.count = 0;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	public int smallerElement(int data)
	{
		TreeNode node = new TreeNode(data);
		if (node != null)
		{
			if (this.root == null)
			{
				this.root = node;
			}
			else
			{
				TreeNode auxiliary = this.root;
				int count = 0;
				// Add new node in binary search tree
				while (auxiliary != null)
				{
					if (data >= auxiliary.data)
					{
						// Update result counter
						if (auxiliary.data == data)
						{
							// When node are same
							count += auxiliary.count;
						}
						else
						{
							count += auxiliary.count + 1;
						}
						if (auxiliary.right == null)
						{
							// Add new node at right child
							auxiliary.right = node;
							return count;
						}
						auxiliary = auxiliary.right;
					}
					else
					{
						// Incress number of left child
						auxiliary.count += 1;
						if (auxiliary.left == null)
						{
							// Add new node at left child
							auxiliary.left = node;
							return count;
						}
						auxiliary = auxiliary.left;
					}
				}
			}
		}
		return 0;
	}
	// Display given array elements
	public void printRecord(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public static void Main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		int[] arr = {
			6 , 2 , 1 , 0 , 2 , 7 , 4 , 0 , 1 , 7 , 3 , 9 , 8
		};
		// Get the number of elements
		int n = arr.Length;
		int[] result = new int[n];
		// Inserting the node in binary search tree and
		// Count number of smaller element in right side
		for (int i = n - 1; i >= 0; --i)
		{
			result[i] = tree.smallerElement(arr[i]);
		}
		Console.Write("\n Array  : ");
		tree.printRecord(arr, n);
		Console.Write("\n Result : ");
		tree.printRecord(result, n);
	}
}

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
package main
import "fmt"
/*
    Go Program for
    Count smaller elements on right side using binary search tree
*/
type TreeNode struct {
	// Data value 
	data int
	// Indicates left and right subtree
	left * TreeNode
	right * TreeNode
	count int
}
func getTreeNode(data int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	me.data = data
	me.left = nil
	me.right = nil
	me.count = 0
	return me
}
type BinarySearchTree struct {
	root * TreeNode
}
func getBinarySearchTree() * BinarySearchTree {
	var me *BinarySearchTree = &BinarySearchTree {}
	me.root = nil
	return me
}
// Adding a new node in binary search tree and
// Returns the number of an element smaller than the given data
func(this *BinarySearchTree) smallerElement(data int) int {
	var node * TreeNode = getTreeNode(data)
	if node != nil {
		if this.root == nil {
			this.root = node
		} else {
			var auxiliary * TreeNode = this.root
			var count int = 0
			// Add new node in binary search tree
			for (auxiliary != nil) {
				if data >= auxiliary.data {
					// Update result counter
					if auxiliary.data == data {
						// When node are same
						count += auxiliary.count
					} else {
						count += auxiliary.count + 1
					}
					if auxiliary.right == nil {
						// Add new node at right child
						auxiliary.right = node
						return count
					}
					auxiliary = auxiliary.right
				} else {
					// Incress number of left child
					auxiliary.count += 1
					if auxiliary.left == nil {
						// Add new node at left child
						auxiliary.left = node
						return count
					}
					auxiliary = auxiliary.left
				}
			}
		}
	}
	return 0
}
// Display given array elements
func(this BinarySearchTree) printRecord(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
func main() {
	var tree * BinarySearchTree = getBinarySearchTree()
	var arr = [] int {
		6,
		2,
		1,
		0,
		2,
		7,
		4,
		0,
		1,
		7,
		3,
		9,
		8,
	}
	// Get the number of elements
	var n int = len(arr)
	var result = make([] int, n)
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	for i := n - 1 ; i >= 0 ; i-- {
		result[i] = tree.smallerElement(arr[i])
	}
	fmt.Print("\n Array  : ")
	tree.printRecord(arr, n)
	fmt.Print("\n Result : ")
	tree.printRecord(result, n)
}

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
<?php
/*
    Php Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode
{
	// Data value 
	public $data;
	// Indicates left and right subtree
	public $left;
	public $right;
	public $count;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
		$this->count = 0;
	}
}
class BinarySearchTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	public	function smallerElement($data)
	{
		$node = new TreeNode($data);
		if ($node != NULL)
		{
			if ($this->root == NULL)
			{
				$this->root = $node;
			}
			else
			{
				$auxiliary = $this->root;
				$count = 0;
				// Add new node in binary search tree
				while ($auxiliary != NULL)
				{
					if ($data >= $auxiliary->data)
					{
						// Update result counter
						if ($auxiliary->data == $data)
						{
							// When node are same
							$count += $auxiliary->count;
						}
						else
						{
							$count += $auxiliary->count + 1;
						}
						if ($auxiliary->right == NULL)
						{
							// Add new node at right child
							$auxiliary->right = $node;
							return $count;
						}
						$auxiliary = $auxiliary->right;
					}
					else
					{
						// Incress number of left child
						$auxiliary->count += 1;
						if ($auxiliary->left == NULL)
						{
							// Add new node at left child
							$auxiliary->left = $node;
							return $count;
						}
						$auxiliary = $auxiliary->left;
					}
				}
			}
		}
		return 0;
	}
	// Display given array elements
	public	function printRecord($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
}

function main()
{
	$tree = new BinarySearchTree();
	$arr = array(6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8);
	// Get the number of elements
	$n = count($arr);
	$result = array_fill(0, $n, 0);
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	for ($i = $n - 1; $i >= 0; --$i)
	{
		$result[$i] = $tree->smallerElement($arr[$i]);
	}
	echo("\n Array  : ");
	$tree->printRecord($arr, $n);
	echo("\n Result : ");
	$tree->printRecord($result, $n);
}
main();

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
/*
    Node JS Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
		this.count = 0;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	smallerElement(data)
	{
		var node = new TreeNode(data);
		if (node != null)
		{
			if (this.root == null)
			{
				this.root = node;
			}
			else
			{
				var auxiliary = this.root;
				var count = 0;
				// Add new node in binary search tree
				while (auxiliary != null)
				{
					if (data >= auxiliary.data)
					{
						// Update result counter
						if (auxiliary.data == data)
						{
							// When node are same
							count += auxiliary.count;
						}
						else
						{
							count += auxiliary.count + 1;
						}
						if (auxiliary.right == null)
						{
							// Add new node at right child
							auxiliary.right = node;
							return count;
						}
						auxiliary = auxiliary.right;
					}
					else
					{
						// Incress number of left child
						auxiliary.count += 1;
						if (auxiliary.left == null)
						{
							// Add new node at left child
							auxiliary.left = node;
							return count;
						}
						auxiliary = auxiliary.left;
					}
				}
			}
		}
		return 0;
	}
	// Display given array elements
	printRecord(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
}

function main()
{
	var tree = new BinarySearchTree();
	var arr = [6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8];
	// Get the number of elements
	var n = arr.length;
	var result = Array(n).fill(0);
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	for (var i = n - 1; i >= 0; --i)
	{
		result[i] = tree.smallerElement(arr[i]);
	}
	process.stdout.write("\n Array  : ");
	tree.printRecord(arr, n);
	process.stdout.write("\n Result : ");
	tree.printRecord(result, n);
}
main();

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
#    Python 3 Program for
#    Count smaller elements on right side using binary search tree
class TreeNode :
	#  Data value 
	#  Indicates left and right subtree
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
		self.count = 0
	

class BinarySearchTree :
	def __init__(self) :
		self.root = None
	
	#  Adding a new node in binary search tree and
	#  Returns the number of an element smaller than the given data
	def smallerElement(self, data) :
		node = TreeNode(data)
		if (node != None) :
			if (self.root == None) :
				self.root = node
			else :
				auxiliary = self.root
				count = 0
				#  Add new node in binary search tree
				while (auxiliary != None) :
					if (data >= auxiliary.data) :
						#  Update result counter
						if (auxiliary.data == data) :
							#  When node are same
							count += auxiliary.count
						else :
							count += auxiliary.count + 1
						
						if (auxiliary.right == None) :
							#  Add new node at right child
							auxiliary.right = node
							return count
						
						auxiliary = auxiliary.right
					else :
						#  Incress number of left child
						auxiliary.count += 1
						if (auxiliary.left == None) :
							#  Add new node at left child
							auxiliary.left = node
							return count
						
						auxiliary = auxiliary.left
					
				
			
		
		return 0
	
	#  Display given list elements
	def printRecord(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	

def main() :
	tree = BinarySearchTree()
	arr = [6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8]
	#  Get the number of elements
	n = len(arr)
	result = [0] * (n)
	i = n - 1
	#  Inserting the node in binary search tree and
	#  Count number of smaller element in right side
	while (i >= 0) :
		result[i] = tree.smallerElement(arr[i])
		i -= 1
	
	print("\n Array  : ", end = "")
	tree.printRecord(arr, n)
	print("\n Result : ", end = "")
	tree.printRecord(result, n)

if __name__ == "__main__": main()

Output

 Array  :   6  2  1  0  2  7  4  0  1  7  3  9  8
 Result :   8  4  2  0  2  4  3  0  0  1  0  1  0
#    Ruby Program for
#    Count smaller elements on right side using binary search tree
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right, :count
	attr_accessor :data, :left, :right, :count
	#  Data value 
	#  Indicates left and right subtree
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
		self.count = 0
	end

end

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	#  Adding a new node in binary search tree and
	#  Returns the number of an element smaller than the given data
	def smallerElement(data) 
		node = TreeNode.new(data)
		if (node != nil) 
			if (self.root == nil) 
				self.root = node
			else
 
				auxiliary = self.root
				count = 0
				#  Add new node in binary search tree
				while (auxiliary != nil) 
					if (data >= auxiliary.data) 
						#  Update result counter
						if (auxiliary.data == data) 
							#  When node are same
							count += auxiliary.count
						else
 
							count += auxiliary.count + 1
						end

						if (auxiliary.right == nil) 
							#  Add new node at right child
							auxiliary.right = node
							return count
						end

						auxiliary = auxiliary.right
					else
 
						#  Incress number of left child
						auxiliary.count += 1
						if (auxiliary.left == nil) 
							#  Add new node at left child
							auxiliary.left = node
							return count
						end

						auxiliary = auxiliary.left
					end

				end

			end

		end

		return 0
	end

	#  Display given array elements
	def printRecord(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

end

def main() 
	tree = BinarySearchTree.new()
	arr = [6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8]
	#  Get the number of elements
	n = arr.length
	result = Array.new(n) {0}
	i = n - 1
	#  Inserting the node in binary search tree and
	#  Count number of smaller element in right side
	while (i >= 0) 
		result[i] = tree.smallerElement(arr[i])
		i -= 1
	end

	print("\n Array  : ")
	tree.printRecord(arr, n)
	print("\n Result : ")
	tree.printRecord(result, n)
end

main()

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
/*
    Scala Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode(
	// Data value 
	var data: Int,
		// Indicates left and right subtree
		var left: TreeNode,
			var right: TreeNode,
				var count: Int)
{
	def this(data: Int)
	{

		this(data, null, null, 0);
	}
}
class BinarySearchTree(var root: TreeNode)
{
	def this()
	{
		
		this(null);
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	def smallerElement(data: Int): Int = {
		var node: TreeNode = new TreeNode(data);
		if (node != null)
		{
			if (this.root == null)
			{
				this.root = node;
			}
			else
			{
				var auxiliary: TreeNode = this.root;
				var count: Int = 0;
				// Add new node in binary search tree
				while (auxiliary != null)
				{
					if (data >= auxiliary.data)
					{
						// Update result counter
						if (auxiliary.data == data)
						{
							// When node are same
							count += auxiliary.count;
						}
						else
						{
							count += auxiliary.count + 1;
						}
						if (auxiliary.right == null)
						{
							// Add new node at right child
							auxiliary.right = node;
							return count;
						}
						auxiliary = auxiliary.right;
					}
					else
					{
						// Incress number of left child
						auxiliary.count += 1;
						if (auxiliary.left == null)
						{
							// Add new node at left child
							auxiliary.left = node;
							return count;
						}
						auxiliary = auxiliary.left;
					}
				}
			}
		}
		return 0;
	}
	// Display given array elements
	def printRecord(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		var arr: Array[Int] = Array(6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8);
		// Get the number of elements
		var n: Int = arr.length;
		var result: Array[Int] = Array.fill[Int](n)(0);
		var i: Int = n - 1;
		// Inserting the node in binary search tree and
		// Count number of smaller element in right side
		while (i >= 0)
		{
			result(i) = tree.smallerElement(arr(i));
			i -= 1;
		}
		print("\n Array  : ");
		tree.printRecord(arr, n);
		print("\n Result : ");
		tree.printRecord(result, n);
	}
}

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0
import Foundation;
/*
    Swift 4 Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode
{
	// Data value 
	var data: Int;
	// Indicates left and right subtree
	var left: TreeNode? ;
	var right: TreeNode? ;
	var count: Int;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
		self.count = 0;
	}
}
class BinarySearchTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	func smallerElement(_ data: Int) -> Int
	{
		let node: TreeNode = TreeNode(data);
		if (self.root == nil)
		{
			self.root = node;
		}
		else
		{
			var auxiliary: TreeNode? = self.root;
			var count: Int = 0;
			// Add new node in binary search tree
			while (auxiliary  != nil)
			{
				if (data >= auxiliary!.data)
				{
					// Update result counter
					if (auxiliary!.data == data)
					{
						// When node are same
						count += auxiliary!.count;
					}
					else
					{
						count += auxiliary!.count + 1;
					}
					if (auxiliary!.right == nil)
					{
						// Add new node at right child
						auxiliary!.right = node;
						return count;
					}
					auxiliary = auxiliary!.right;
				}
				else
				{
					// Incress number of left child
					auxiliary!.count += 1;
					if (auxiliary!.left == nil)
					{
						// Add new node at left child
						auxiliary!.left = node;
						return count;
					}
					auxiliary = auxiliary!.left;
				}
			}
		}
		return 0;
	}
	// Display given array elements
	func printRecord(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
}
func main()
{
	let tree: BinarySearchTree = BinarySearchTree();
	let arr: [Int] = [6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8];
	// Get the number of elements
	let n: Int = arr.count;
	var result: [Int] = Array(repeating: 0, count: n);
	var i: Int = n - 1;
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	while (i >= 0)
	{
		result[i] = tree.smallerElement(arr[i]);
		i -= 1;
	}
	print("\n Array  : ", terminator: "");
	tree.printRecord(arr, n);
	print("\n Result : ", terminator: "");
	tree.printRecord(result, n);
}
main();

Output

 Array  :   6  2  1  0  2  7  4  0  1  7  3  9  8
 Result :   8  4  2  0  2  4  3  0  0  1  0  1  0
/*
    Kotlin Program for
    Count smaller elements on right side using binary search tree
*/
class TreeNode
{
	// Data value 
	var data: Int;
	// Indicates left and right subtree
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	var count: Int;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
		this.count = 0;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Adding a new node in binary search tree and
	// Returns the number of an element smaller than the given data
	fun smallerElement(data: Int): Int
	{
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary: TreeNode ? = this.root;
			var count: Int = 0;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data >= auxiliary.data)
				{
					// Update result counter
					if (auxiliary.data == data)
					{
						// When node are same
						count += auxiliary.count;
					}
					else
					{
						count += auxiliary.count + 1;
					}
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return count;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					// Incress number of left child
					auxiliary.count += 1;
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return count;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
		return 0;
	}
	// Display given array elements
	fun printRecord(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	val arr: Array < Int > = arrayOf(6, 2, 1, 0, 2, 7, 4, 0, 1, 7, 3, 9, 8);
	// Get the number of elements
	val n: Int = arr.count();
	var result: Array < Int > = Array(n)
	{
		0
	};
	var i: Int = n - 1;
	// Inserting the node in binary search tree and
	// Count number of smaller element in right side
	while (i >= 0)
	{
		result[i] = tree.smallerElement(arr[i]);
		i -= 1;
	}
	print("\n Array  : ");
	tree.printRecord(arr, n);
	print("\n Result : ");
	tree.printRecord(result, n);
}

Output

 Array  :  6 2 1 0 2 7 4 0 1 7 3 9 8
 Result :  8 4 2 0 2 4 3 0 0 1 0 1 0

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved