C++ program to find median of binary search tree
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* Structure of node */
template <typename T>
struct Node {
T data;
Node<T>* left;
Node<T>* right;
};
/* Creating new node with value as x */
template <typename T>
Node<T>* NewNode(T x)
{
Node<T>* node = new Node<T>;
node->data = x;
return node;
}
/* Inserting node in Binary search Tree */
template <typename T>
Node<T>* insert(Node<T>* root, T x)
{
/* If node is NULL create new node and return */
if (root == NULL)
return NewNode<T>(x);
/* If x is samller than current node go to left sub tree */
if (root->data > x)
root->left = insert<T>(root->left, x);
/* If x is greater than current node go to right sub tree */
else if (root->data <x)
root->right = insert<T>(root->right, x);
return root;
}
/* Traversing the tree in inorder manner and storing them in vector */
/* Traversing a BST in inorder will give nodes in sorted order */
template <typename T>
void inorder(const Node<T>* root, std::vector<T>& a)
{
if (root == NULL)
return;
inorder(root->left, a);
a.push_back(root->data);
inorder(root->right, a);
}
//finding the median
template <typename T>
double median(Node<T> * root) {
std::vector<T> a;
inorder(root,a);
if(a.size()%2!=0) //if number of nodes is odd
return a[a.size() / 2];
else
return ((a[a.size()/2]+a[(a.size()/2)-1])/2);//if no. of nodes is even
}
int main()
{
Node<int>* root = NULL;
root = insert<int>(root, 28);
insert<int>(root, 25);
insert<int>(root, 20);
insert<int>(root, 27);
insert<int>(root, 30);
insert<int>(root, 36);
insert<int>(root, 40);
insert<int>(root, 80);
std::cout << "MEDIAN OF GIVEN BST: " << median(root) << std::endl;
}
// Inorder traversal of BST will give sorted list of node after that find the median
// after that a normal formula to find median
/* 28
/ \
25 36
/ \ / \
20 27 30 40
\
80
*/
//output:: median=29
Comments