The question is to obtain median of given elements. If odd then simply return the middle element else return the mean of the n/2 and n/2 + 1 element.

The problem is that it is always returning 1 as the median, which probably means that rotation is not happening as 1 was my first input.

I know it is a famous leet code question, but i have written all my code by myself and there is no one else in the discussion panel whose code is written on avl tree from scratch. Code:

``````'''
class Node{
int data;
Node left, right;
int height;
Node(int d){
this.data = d;
this.left = this.right = null;
this.height = 1;
}
Node(){
this.left = this.right = null;
}
}

class MedianFinder {
static Node root;
MedianFinder(){
root = new Node();
}

insert(root, num);
}

public static Node insert(Node root, int num){
if(root == null)
return (new Node(num));

if(root.data < num){
root.right = insert(root.right, num);
}
else if(root.data > num)
root.left = insert(root.left, num);

root.height = max(height(root.left) , height(root.right)) + 1;

int balance = get_balance(root);
// if left left
if(balance > 2 && num < root.left.data){
return rightRotation(root);
}
// left right case
if(balance > 2 && num > root.left.data){
leftRotation(root.left);
return rightRotation(root);
}
// right right case
if(balance < -1 && num > root.right.data)
return leftRotation(root);

// right left case
if(balance < -1 && num < root.right.data){
rightRotation(root.right);
return leftRotation(root);
}
return root;

}

public static Node rightRotation(Node node){
Node temp = node.left;
Node tempright = temp.right;
temp.right = node;
node.left = tempright;

node.height = max(height(node.left), height(node.right)) + 1;
temp.height = max(height(temp.left), height(temp.right)) + 1;

return temp;
}

public static Node leftRotation(Node node){
Node temp = node.right;
Node templeft = temp.left;
temp.left = node;
node.right = templeft;

node.height = max(height(node.left), height(node.right)) + 1;
temp.height = max(height(temp.left), height(temp.right)) + 1;

return temp;
}

public static int get_balance(Node node){
if(node == null)
return 0;
return height(node.left) - height(node.right);
}

public static int height(Node node){
if(node == null)
return 0;
return node.height;
}
public static int max(int a, int b){
return a>b?a:b;
}

public double findMedian() {

if(height(root.left) == height(root.right))
return root.data;
return (root.data + root.right.data) / 2;

}

public static int count(Node node){
if(node == null)
return 0;
return 1 + count(node.left) + count(node.right);
}
}

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();