Cartesian Tree

Given a sequence of numbers, there exists a binary min-heap whose inorder traversal is that sequence. This is known as the Cartesian tree for that sequence.

For more detail, click here

Implementation

class CartesionTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

public Tree(int data){
this.data = data;
}

//cartesian tree
public static Tree createTree(int []a, int left, int right){
if(right < left)
return null;

int min = Integer.MAX_VALUE;
int minIndex = -1;

for(int i = left; i <= right; i++){
if(a[i] < min){
min = a[i];
minIndex = i;
}
}

Tree root = new Tree(a[minIndex]);
root.left = createTree(a, left, minIndex - 1);
root.right = createTree(a, minIndex + 1, right);

return root;
}

//in-order traversal
public static void inorder(Tree root){
if(root != null){
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}
}
}

public static void main(String []args){
int a[] = {9,3,7,1,8,12,10,20,15,18,5};

Tree root = Tree.createTree(a, 0, a.length - 1);
Tree.inorder(root);
}
}