Find median of binary search tree
Here given code implementation process.
//C Program
//Find median of binary search tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left,*right;
};
//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));
if(new_node!=NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL;//Initially node right-pointer is NULL
if(*root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while(find != NULL)
{
if(find -> data > data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
}
int counter(struct Node*root)
{
if(root != NULL)
{
return counter(root->left)+counter(root->right)+1;
}
return 0;
}
void get_elements(struct Node*root,int *auxiliary,int *index)
{
if(root != NULL)
{
get_elements(root->left,auxiliary,index);
auxiliary[*index]+=root->data;
(*index)++;
get_elements(root->right,auxiliary,index);
}
}
void find_median(struct Node*root)
{
if(root != NULL)
{
int size=counter(root);
int *auxiliary=(int*)calloc(size,sizeof(int));
int index=0;
get_elements(root,auxiliary,&index);
int result=0;
if(size%2!=0)
{
index=(size)/2;
result=auxiliary[index];
}
else
{
result=(auxiliary[(size-1)/2] + auxiliary[(size)/2])/2;
}
printf("\nMedian : %d\n",result );
free(auxiliary);
auxiliary=NULL;
}
}
void inorder(struct Node*root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%3d ",root->data );
inorder(root->right);
}
}
int main(){
struct Node*root = NULL;
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
add(&root,5);
add(&root,3);
add(&root,9);
add(&root,1);
add(&root,4);
add(&root,8);
add(&root,11);
add(&root,-3);
add(&root,2);
add(&root,7);
add(&root,12);
inorder(root);
find_median(root);//5
//case 2
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
add(&root,13);
inorder(root);
find_median(root); //6
return 0;
}
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
/*
C++ Program
Find median of binary search tree
*/
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree {
public:
Node *root;
int counter;
BinarySearchTree() {
this->root = NULL;
this->counter = 0;
}
void add(int value) {
Node *new_node = new Node(value);
if (new_node != NULL) {
if (this->root == NULL) {
this->root = new_node;
} else {
Node *find = this->root;
while (find != NULL) {
if (find->data >= value) {
if (find->left == NULL) {
find->left = new_node;
break;
} else {
find = find->left;
}
} else {
if (find->right == NULL) {
find->right = new_node;
break;
} else {
find = find->right;
}
}
}
}
} else {
cout << "\nMemory Overflow\n";
}
}
int counter_nodes(Node *head) {
if (head != NULL) {
return this->counter_nodes(head->left) + this->counter_nodes(head->right) + 1;
}
return 0;
}
void get_elements(Node *head, int auxiliary[]) {
if (head != NULL) {
this->get_elements(head->left, auxiliary);
auxiliary[this->counter] += head->data;
this->counter++;
this->get_elements(head->right, auxiliary);
}
}
void find_median() {
if (this->root != NULL) {
int size = this->counter_nodes(this->root);
int *auxiliary = new int[size];
this->counter = 0;
this->get_elements(this->root, auxiliary);
int result = 0;
if (size % 2 != 0) {
result = auxiliary[(size) / 2];
} else {
result = (auxiliary[(size - 1) / 2] + auxiliary[(size) / 2]) / 2;
}
cout << "\nMedian : " << result << " \n";
}
}
void inorder(Node *head) {
if (head != NULL) {
this->inorder(head->left);
cout << head->data << " ";
this->inorder(head->right);
}
}
};
int main() {
BinarySearchTree obj;
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.inorder(obj.root);
obj.find_median();
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
obj.add(13);
obj.inorder(obj.root);
obj.find_median();
return 0;
}
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
//Java program
//Find median of binary search tree
class Node {
public int data;
public Node left;
public Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
public Node root;
public int counter;
BinarySearchTree()
{
root = null;
counter = 0;
}
//insert a node in BST
public void add(int value)
{
//Create a dynamic node of binary search tree
Node new_node = new Node(value);
if(new_node != null)
{
if(root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node find = root;
//add new node to proper position
while(find != null)
{
if(find.data >= value)
{
if(find.left==null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if(find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
System.out.print("\nMemory Overflow\n");
}
}
int counter_nodes(Node head)
{
if(head != null)
{
return counter_nodes(head.left)+counter_nodes(head.right)+1;
}
return 0;
}
public void get_elements(Node head,int []auxiliary)
{
if(head != null)
{
get_elements(head.left,auxiliary);
auxiliary[this.counter]+=head.data;
this.counter++;
get_elements(head.right,auxiliary);
}
}
public void find_median()
{
if(root != null)
{
int size=counter_nodes(root);
int []auxiliary=new int[size];
this.counter = 0;
get_elements(root,auxiliary);
int result=0;
if(size%2!=0)
{
result=auxiliary[(size)/2];
}
else
{
result=(auxiliary[(size-1)/2] + auxiliary[(size)/2])/2;
}
System.out.print("\nMedian : "+result+" \n" );
}
}
public void inorder(Node head) {
if (head != null) {
inorder(head.left);
System.out.print(head.data + " ");
inorder(head.right);
}
}
public static void main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.inorder(obj.root);
obj.find_median();//5
//case 2
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
obj.add(13);
obj.inorder(obj.root);
obj.find_median(); //6
}
}
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
//C# program
//Find median of binary search tree
using System;
public class Node {
public int data;
public Node left;
public Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
public Node root;
public int counter;
BinarySearchTree()
{
root = null;
counter = 0;
}
//insert a node in BST
public void add(int value)
{
//Create a dynamic node of binary search tree
Node new_node = new Node(value);
if(new_node != null)
{
if(root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
Node find = root;
//add new node to proper position
while(find != null)
{
if(find.data >= value)
{
if(find.left==null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if(find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
Console.Write("\nMemory Overflow\n");
}
}
int counter_nodes(Node head)
{
if(head != null)
{
return counter_nodes(head.left)+counter_nodes(head.right)+1;
}
return 0;
}
public void get_elements(Node head,int []auxiliary)
{
if(head != null)
{
get_elements(head.left,auxiliary);
auxiliary[this.counter]+=head.data;
this.counter++;
get_elements(head.right,auxiliary);
}
}
public void find_median()
{
if(root != null)
{
int size=counter_nodes(root);
int []auxiliary=new int[size];
this.counter = 0;
get_elements(root,auxiliary);
int result=0;
if(size%2!=0)
{
result=auxiliary[(size)/2];
}
else
{
result=(auxiliary[(size-1)/2] + auxiliary[(size)/2])/2;
}
Console.Write("\nMedian : "+result+" \n" );
}
}
public void inorder(Node head) {
if (head != null) {
inorder(head.left);
Console.Write(head.data + " ");
inorder(head.right);
}
}
public static void Main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.inorder(obj.root);
obj.find_median();//5
//case 2
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
obj.add(13);
obj.inorder(obj.root);
obj.find_median(); //6
}
}
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
# Python 3 Program
# Find median of binary search tree
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
self.counter = 0
def add(self, value) :
new_node = Node(value)
if (new_node != None) :
if (self.root == None) :
self.root = new_node
else :
find = self.root
while (find != None) :
if (find.data >= value) :
if (find.left == None) :
find.left = new_node
break
else :
find = find.left
else :
if (find.right == None) :
find.right = new_node
break
else :
find = find.right
else :
print("\nMemory Overflow\n")
def counter_nodes(self, head) :
if (head != None) :
return self.counter_nodes(head.left) + self.counter_nodes(head.right) + 1
return 0
def get_elements(self, head, auxiliary) :
if (head != None) :
self.get_elements(head.left, auxiliary)
auxiliary[self.counter] += head.data
self.counter += 1
self.get_elements(head.right, auxiliary)
def find_median(self) :
if (self.root != None) :
size = self.counter_nodes(self.root)
auxiliary = [0]*size
self.counter = 0
self.get_elements(self.root, auxiliary)
result = 0
if (size % 2 != 0) :
result = auxiliary[int((size) / 2)]
else :
result = int((auxiliary[int((size - 1) / 2)] + auxiliary[int((size) / 2)]) / 2)
print("\nMedian : ", result ," \n")
def inorder(self, head) :
if (head != None) :
self.inorder(head.left)
print(head.data ,end=" ")
self.inorder(head.right)
def main() :
obj = BinarySearchTree()
#
# 5
# / \
# 3 9
# / \ / \
# 1 4 8 11
# / \ / \
# -3 2 7 12
#
obj.add(5)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(4)
obj.add(8)
obj.add(11)
obj.add(-3)
obj.add(2)
obj.add(7)
obj.add(12)
obj.inorder(obj.root)
obj.find_median()
obj.add(13)
#
# 5
# / \
# 3 9
# / \ / \
# 1 4 8 11
# / \ / \
# -3 2 7 12
# \
# 13
# (5+7)/2 = 6
#
obj.inorder(obj.root)
obj.find_median()
if __name__ == "__main__":
main()
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
# Ruby Program
# Find median of binary search tree
class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end
class BinarySearchTree
attr_reader :root, :counter
attr_accessor :root, :counter
def initialize()
@root = nil
@counter = 0
end
def add(value)
new_node = Node.new(value)
if (new_node != nil)
if (@root == nil)
@root = new_node
else
find = @root
while (find != nil)
if (find.data >= value)
if (find.left == nil)
find.left = new_node
break
else
find = find.left
end
else
if (find.right == nil)
find.right = new_node
break
else
find = find.right
end
end
end
end
else
print("\nMemory Overflow\n")
end
end
def counter_nodes(head)
if (head != nil)
return self.counter_nodes(head.left) + self.counter_nodes(head.right) + 1
end
return 0
end
def get_elements(head, auxiliary)
if (head != nil)
self.get_elements(head.left, auxiliary)
auxiliary[self.counter] += head.data
self.counter += 1
self.get_elements(head.right, auxiliary)
end
end
def find_median()
if (@root != nil)
size = self.counter_nodes(@root)
auxiliary = Array.new(size,0)
self.counter = 0
self.get_elements(@root, auxiliary)
result = 0
if (size % 2 != 0)
result = auxiliary[(size) / 2]
else
result = (auxiliary[(size - 1) / 2] + auxiliary[(size) / 2]) / 2
end
print("\nMedian : ", result ," \n")
end
end
def inorder(head)
if (head != nil)
self.inorder(head.left)
print(head.data ," ")
self.inorder(head.right)
end
end
end
def main()
obj = BinarySearchTree.new()
#
# 5
# / \
# 3 9
# / \ / \
# 1 4 8 11
# / \ / \
# -3 2 7 12
#
obj.add(5)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(4)
obj.add(8)
obj.add(11)
obj.add(-3)
obj.add(2)
obj.add(7)
obj.add(12)
obj.inorder(obj.root)
obj.find_median()
obj.add(13)
#
# 5
# / \
# 3 9
# / \ / \
# 1 4 8 11
# / \ / \
# -3 2 7 12
# \
# 13
# (5+7)/2 = 6
#
obj.inorder(obj.root)
obj.find_median()
end
main()
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
<?php
/*
Php Program
Find median of binary search tree
*/
class Node {
public $data;
public $left;
public $right;
function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
class BinarySearchTree {
public $root;
public $counter;
function __construct() {
$this->root = null;
$this->counter = 0;
}
public function add($value) {
$new_node = new Node($value);
if ($new_node != null) {
if ($this->root == null) {
$this->root = $new_node;
} else {
$find = $this->root;
while ($find != null) {
if ($find->data >= $value) {
if ($find->left == null) {
$find->left = $new_node;
break;
} else {
$find = $find->left;
}
} else {
if ($find->right == null) {
$find->right = $new_node;
break;
} else {
$find = $find->right;
}
}
}
}
} else {
echo("\nMemory Overflow\n");
}
}
function counter_nodes($head) {
if ($head != null) {
return $this->counter_nodes($head->left) + $this->counter_nodes($head->right) + 1;
}
return 0;
}
public function get_elements($head, &$auxiliary) {
if ($head != null) {
$this->get_elements($head->left, $auxiliary);
$auxiliary[$this->counter] += $head->data;
$this->counter++;
$this->get_elements($head->right, $auxiliary);
}
}
public function find_median() {
if ($this->root != null) {
$size = $this->counter_nodes($this->root);
$auxiliary = array_fill(0, $size, 0);
$this->counter = 0;
$this->get_elements($this->root, $auxiliary);
$result = 0;
if ($size % 2 != 0) {
$result = $auxiliary[intval(($size) / 2)];
} else {
$result = intval( ( ($auxiliary[intval(($size - 1) / 2)] + $auxiliary[intval(($size) / 2)])) / 2);
}
echo("\nMedian : ". $result ." \n");
}
}
public function inorder($head) {
if ($head != null) {
$this->inorder($head->left);
echo($head->data ." ");
$this->inorder($head->right);
}
}
}
function main() {
$obj = new BinarySearchTree();
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
$obj->add(5);
$obj->add(3);
$obj->add(9);
$obj->add(1);
$obj->add(4);
$obj->add(8);
$obj->add(11);
$obj->add(-3);
$obj->add(2);
$obj->add(7);
$obj->add(12);
$obj->inorder($obj->root);
$obj->find_median();
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
$obj->add(13);
$obj->inorder($obj->root);
$obj->find_median();
}
main();
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
/*
Node Js Program
Find median of binary search tree
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
this.counter = 0;
}
add(value) {
var new_node = new Node(value);
if (new_node != null) {
if (this.root == null) {
this.root = new_node;
} else {
var find = this.root;
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
find = find.right;
}
}
}
}
} else {
process.stdout.write("\nMemory Overflow\n");
}
}
counter_nodes(head) {
if (head != null) {
return this.counter_nodes(head.left) + this.counter_nodes(head.right) + 1;
}
return 0;
}
get_elements(head, auxiliary) {
if (head != null) {
this.get_elements(head.left, auxiliary);
auxiliary[this.counter] += head.data;
this.counter++;
this.get_elements(head.right, auxiliary);
}
}
find_median() {
if (this.root != null) {
var size = this.counter_nodes(this.root);
var auxiliary = Array(size).fill(0);
this.counter = 0;
this.get_elements(this.root, auxiliary);
var result = 0;
if (size % 2 != 0) {
result = auxiliary[parseInt((size) / 2)];
} else {
result = parseInt((auxiliary[parseInt((size - 1) / 2)] + auxiliary[parseInt((size) / 2)]) / 2);
}
process.stdout.write("\nMedian : " + result + " \n");
}
}
inorder(head) {
if (head != null) {
this.inorder(head.left);
process.stdout.write(head.data + " ");
this.inorder(head.right);
}
}
}
function main() {
var obj = new BinarySearchTree();
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.inorder(obj.root);
obj.find_median();
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
obj.add(13);
obj.inorder(obj.root);
obj.find_median();
}
main();
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
/*
Swift 4 Program
Find median of binary search tree
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree {
var root: Node? ;
var counter: Int;
init() {
self.root = nil;
self.counter = 0;
}
func add(_ value: Int) {
let new_node: Node? = Node(value);
if (new_node != nil) {
if (self.root == nil) {
self.root = new_node;
} else {
var find: Node? = self.root;
while (find != nil) {
if (find!.data >= value) {
if (find!.left == nil) {
find!.left = new_node;
break;
} else {
find = find!.left;
}
} else {
if (find!.right == nil) {
find!.right = new_node;
break;
} else {
find = find!.right;
}
}
}
}
} else {
print("\nMemory Overflow\n");
}
}
func counter_nodes(_ head: Node? ) -> Int {
if (head != nil) {
return self.counter_nodes(head!.left) + self.counter_nodes(head!.right) + 1;
}
return 0;
}
func get_elements(_ head: Node? , _ auxiliary : inout [Int] ) {
if (head != nil) {
self.get_elements(head!.left, &auxiliary);
auxiliary[self.counter] += head!.data;
self.counter += 1;
self.get_elements(head!.right, &auxiliary);
}
}
func find_median() {
if (self.root != nil) {
let size: Int = self.counter_nodes(self.root);
var auxiliary: [Int] = Array(repeating:0,count:size);
self.counter = 0;
self.get_elements(self.root, &auxiliary);
var result: Int = 0;
if (size % 2 != 0) {
result = auxiliary[(size) / 2];
} else {
result = (auxiliary[(size - 1) / 2] + auxiliary[(size) / 2]) / 2;
}
print("\nMedian : ", result );
}
}
func inorder(_ head: Node? ) {
if (head != nil) {
self.inorder(head!.left);
print(head!.data ,terminator:" ");
self.inorder(head!.right);
}
}
}
func main() {
let obj: BinarySearchTree = BinarySearchTree();
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.inorder(obj.root);
obj.find_median();
obj.add(13);
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
\
13
(5+7)/2 = 6
*/
obj.inorder(obj.root);
obj.find_median();
}
main();
Output
-3 1 2 3 4 5 7 8 9 11 12
Median : 5
-3 1 2 3 4 5 7 8 9 11 12 13
Median : 6
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