[Solved] Strange Median Contest Problem

Strange Median!: You are given a binary search tree. You task is to find the median of sub tree of K^th smallest node of the tree.

Input Format:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains two lines of input. The first line contains number of nodes and a value K separated by space. The second line contains value of nodes.

Output Format:
For each testcase, in a new line, print the median of sub tree of K^th smallest node of the tree.

Your Task:
This is a function problem. You don’t have to take any input. You just need to complete the function median that takes node and K as parameters.

Constraints:
1 <= T <= 30
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000
1 <= K <= Number of nodes 

Example:
Input:
1
12 9
50 25 75 15 45 90 11 20 30 49 80 100
Output:
85

Explanation:
Testcase1: The tree is like this:
                                  50
                                 /     \
                             25        75
                           /      \              \
                          15       45             90
                         /    \       /  \        /     \
                      11     20   30    49  80      100
K=9. So the 9th smallest number is 75. The values of this subtree are 75 80 90 100. Now, the median of this is (80+90)/2 = 85

Solution

void inOrderBST(Node *root,vector<Node *>&v)
{
    if(root==NULL)
    return;
    
    inOrderBST(root->left,v);
    v.push_back(root);
    inOrderBST(root->right,v);
}

int median(Node *root,int k)
{
    if(root==NULL)
    return -1;
    
    vector<Node *>v;
    
    inOrderBST(root,v);
    
    Node *subtreeRoot=v[k-1];
    
    v.clear();
    
    inOrderBST(subtreeRoot,v);
    
    int len=v.size();
    
    if(len%2!=0)
    {
        return v[len/2]->data;
    }
    else
    {
         return (v[len/2]->data+v[(len/2)-1]->data)/2;
    }
    
}

class GfG {
    ArrayList<Node> nodesList;
    void traverseInorder(Node node) {
        if(node==null)return;
        traverseInorder(node.left);
        nodesList.add(node);
        traverseInorder(node.right);
        return;
    }

    int median(Node root, int k) {
        if(root==null)return -1;
        // Code here
        nodesList = new ArrayList<>();
        traverseInorder(root);
        Node subTree = nodesList.get(k-1);
        nodesList = new ArrayList<>();
        traverseInorder(subTree);
        int len=nodesList.size();
        if(len%2!=0){
            return nodesList.get(len/2).data;
        } else {
            return (nodesList.get(len/2).data+nodesList.get((len/2)-1).data)/2;
        }
    }
}

def median(root, k):
    if(root == None):
        return -1
    global v
    v=[]
    inorder(root)
    subtreeRoot = v[k-1]
    v=[]
    inorder(subtreeRoot)
    l = len(v)
    # print(l)
    if(l%2!=0):
        # print("@")
        return v[l//2].data
    else:
        return (v[l//2].data + v[(l//2)-1].data)//2

Happy Learning – If you require any further information, feel free to contact me.