C++ program to find median of binary search tree














































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