Niketan R Pansare

import java.io.*;
import java.util.StringTokenizer;
import java.util.Random;

/**
* Implements Min Leftist tree
*/
public class MinLeftistTree{

/**
* Root of the min leftist tree
*/
public MinLeftistTreeNode root = null;

/**
* Inserts an integer data into min leftist tree
*/
public void insert(int data){
MinLeftistTreeNode newNode = new MinLeftistTreeNode();
newNode.data = data;

root = meld(root, newNode);
}

/**
* Visit function - used to display the elements of tree
*/
private void visit(MinLeftistTreeNode n1, Queue q){
System.out.print(", " + n1.data);
n1.visited = true;
q.insert(n1);
}

/**
* Displays the elements of tree - Level order
*/
public void display(){
//BFS
if(root != null){
Queue q = new Queue();
MinLeftistTreeNode temp = root;

//Visit start Node
System.out.print("[" + temp.data);
temp.visited = true;
q.insert(temp);


//while(Queue not empty)
while(!q.isEmpty()){
temp = q.remove();


if( temp.leftChild != null){
visit(temp.leftChild, q);
}
if(temp.rightChild != null){
visit(temp.rightChild, q);
}
}

System.out.print("]" );

}
else{
System.out.println("MinLeftist tree is empty");
}
}

/**
* Removes min element from the min leftist tree
*
*/
public int removeMin(){
if(root == null){
//System.out.println("Min Leftist tree is empty. Hence cannot perform a removeMin");
return -1;
}
else{
int returnValue = root.data;

root = meld(root.leftChild, root.rightChild);

return returnValue;
}

}

/**
* It checks for s-violation. It returns corrected node if there is s-violation.
*/
public MinLeftistTreeNode checkForSViolation(MinLeftistTreeNode n1){
if(n1.leftChild == null && n1.rightChild == null){
n1.sValue = 1;
}
else if(n1.leftChild == null){
n1.leftChild = n1.rightChild;
n1.rightChild = null;
n1.sValue = 1;
}
else if(n1.rightChild == null){
n1.sValue = 1;
}
else if(n1.leftChild.sValue < n1.rightChild.sValue){
MinLeftistTreeNode temp = n1.leftChild;
n1.leftChild = n1.rightChild;
n1.rightChild = temp;
n1.sValue = n1.leftChild.sValue < n1.rightChild.sValue ? n1.leftChild.sValue + 1 : n1.rightChild.sValue + 1;
}
else{
n1.sValue = n1.leftChild.sValue < n1.rightChild.sValue ? n1.leftChild.sValue + 1 : n1.rightChild.sValue + 1;
}
return n1;
}

/**
* Melds two trees n1, n2 and returns melded tree
*/
public MinLeftistTreeNode meld(MinLeftistTreeNode n1, MinLeftistTreeNode n2){
//If u meld null with something, u get something :)
if(n1 == null && n2 == null){
return null;
}
else if(n1 == null){
return n2;
}
else if(n2 == null){
return n1;
}
else{
if(n1.data < n2.data){
//n1 is smaller

MinLeftistTreeNode n3 = meld(n1.rightChild, n2);

n1.rightChild = n3;

n1 = checkForSViolation(n1);

return n1;
}
else{
//n2 is smaller


MinLeftistTreeNode n3 = meld(n2.rightChild, n1);

n2.rightChild = n3;

n2 = checkForSViolation(n2);

return n2;
}
}

}

}

/**
* It represents node of min leftist tree
*
*/
class MinLeftistTreeNode{
public int sValue = 0;

public boolean visited = false;

public MinLeftistTreeNode leftChild = null;

public MinLeftistTreeNode rightChild = null;

public int data = 0;

public MinLeftistTreeNode(){
if(leftChild == null || rightChild == null){
sValue = 1;
}
else{
sValue = leftChild.sValue < rightChild.sValue ? leftChild.sValue + 1 : rightChild.sValue + 1;
}

}
}



/**
* Simple queue used, while implementing MinLeftist tree
*
*/
class Queue{
public QueueElement head = null;

/**
* Returns true is queue is empty, else false
*/
public boolean isEmpty(){
if(head == null)
return true;
else
return false;
}

/**
* Inserts a min leftist tree node into the queue
*
*/
public void insert(MinLeftistTreeNode data){
if(head == null){
head = new QueueElement();
head.data = data;
}
else{
QueueElement temp = head;
while(temp.next != null){
temp = temp.next;
}
QueueElement newNode = new QueueElement();
newNode.data = data;

temp.next = newNode;

}
}

/**
* Pops and returns the head (first element) of queue
*/
public MinLeftistTreeNode remove(){
MinLeftistTreeNode temp = head.data;
head = head.next;
return temp;
}
}

/**
* It represents elements of queue
*/
class QueueElement{
public MinLeftistTreeNode data = null;
public QueueElement next = null;
}