### c++ program to find median of binary search tree in o(n)

DESCRPTION:

Given a Binary Search Tree, find median of it.

If no. of nodes are even: then median = ((n/2th node + (n+1)/2th node) /2
If no. of nodes are odd : then median = (n+1)/2th node.

```Given BST(with odd no. of nodes) is :
6
/    \
3       8
/   \    /  \
1     4  7    9

Inorder of Given BST will be : 1, 3, 4, 6, 7, 8, 9
So, here median will 6.

Given BST(with even no. of nodes) is :
6
/    \
3       8
/   \    /
1     4  7

Inorder of Given BST will be : 1, 3, 4, 6, 7, 8
So, here median will  (4+6)/2 = 5.```
CODE:

#include<iostream>
using namespace std;
struct node
int number;
struct node* left, *right;
};

// to create a new binary search tree node
struct node *newnode(int item)
struct node *temp =  new node;
temp->number = item;
temp->left = temp->right = NULL;
return temp;

//  to insert a new node in binary search tree
struct node* insert(struct node* node, int a)
// If the tree is empty then return a new node
if (node == NULL) return newnode(a);

/* Otherwise, recur down the tree */
if (a< node->number)
node->left  = insert(node->left,a);
else if (a> node->number)
node->right = insert(node->right,a);

//return the  node
return node;

// function to count nodes in a  binary search tree
int count(struct node *root)
struct node *current, *pre;

// initialise count of nodes as 0
int d= 0;

if (root == NULL)
return d;

current = root;
while (current != NULL)
{
if (current->left == NULL)
{
d++;

current = current->right;
}
else
{
pre = current->left;

while (pre->right != NULL &&
pre->right != current)
pre = pre->right;

if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}

else
{
pre->right = NULL;
d++;
current = current->right;
}
}
}

return d;

//function to find median in binary search tree
int median(struct node *root)
if (root == NULL)
return 0;

int d= count(root);
int t= 0;
struct node *current = root, *pre, *prev;

while (current != NULL)
{
if (current->left == NULL)
{
t++;

if (d% 2 != 0 && t== (d+1)/2)
return prev->number;
else if (d% 2 == 0 && t== (d/2)+1)
return (prev->number+ current->number)/2;
prev = current;
current = current->right;
}
else
{
pre = current->left;
while (pre->right != NULL && pre->right != current)
pre = pre->right;
if (pre->right == NULL)
{
pre->right = current;
current = current->left;
}
else
{
pre->right = NULL;
prev = pre;
t++;
if (d% 2 != 0 && t== (d+1)/2 )
return current->number;

else if (d%2==0 && t== (d/2)+1)
return (prev->number+current->number)/2;
prev = current;
current = current->right;

}
}
}
// main of the function
int main()

struct node *root = NULL;
root = insert(root,32);
insert(root,36);
insert(root,5);
insert(root,22);
insert(root,98);
insert(root,50);
insert(root,100);
insert(root,25);
insert(root,36);
cout << "\nmedian of bianry search tree is "
<<median(root);
cout<<" using o(n) approach";
return 0;

OUTPUT OF THE CODE:

median of the binary search tree is 34 using o(n) approach

#### More Articles of Vidushi Sinha:

Name Views Likes
c++ program to find median of binary search tree in o(n) 982 0