Posted on by Kalkicode
Code Binary Search Tree

# 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_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``````

## Comment

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.

Categories
Relative Post