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














































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

Comments