CareerCup

This Solution is similar to above one, but more easier to understand in recursion point of view:
1. Find nodes with biggest j (we call it pivot) in node array.
2. Partition the array into two parts, all elements in left part have i smaller than i of pivot while all elements in right part have i bigger than i of pivot.
3. Use pivot as root of tree.
4. set left sub-tree of root as a tree built from left part of array.
5. set right sub-tree of root as a tree built from right part of array.
6. return root.

Average time complexity: O(NlogN)
Worst time complecity: O(N^2)

A treap is the correct way to implement this. Add the BST nodes one by one according to the usual rules. After each, consider the heap property of the new BST node and its parent. If the heap property is violated, perform tree rotations until the new node is the root or the heap property is satisfied.

Runtime is O(n*lg n), since each of the n BST insertions takes (lg n)
and no node must be rotated (lg n) times

The BST may be horribly unbalanced, but that wasn't a requirement, so there.

I think we can do it the following way:
Sort the nodes in decreasing order of their j values and then simply build the BST according to the i values starting from the first node in the obtained sorted list. The first node will be the root.
For example, let the given nodes (i,j pairs) be:
(12,6) (18,25) (19,10) (17,5) (19,10) i.e. 5 nodes
nodes after sorting in decreasing order according to j values:
(18,25) (16,11) (19,10) (12,6) (17,5)
So the tree would be something like this:
(18,25)
|
| |
(16,11) (19,10)
|
| |
(12,6) (17,5)
As we can see, the i values obey BST property and the j values obey MaxHeap property.
Tell me, what do u think?

@vipul can write the code for it..i need to aware for Time Complexity ..???

If the tree has heap property, we should just concentrate on creating the heap. We can create only one heap from a node set while there are n different BST. If at any time it does not follow BST property, then such a tree cannot be created through the given set of nodes.

1. Sort the node by the first value and keep it in array 1, coz the mid-order reversal of a binary search tree is a fully sorted array.
2. Sort the node by the second value and keep it in array 2.
So the process becomes to keep finding the node in array 1 which has the smallest value in array 2, the left-side of that node in array 1 is its left subtree and the right-side is the right subtree.

Recursive alogrithm in array 1 would be more complex in time because for each part it is necessary to find the node which has the smallest second value in the sub-part.
But if you recursively construct the tree via array 2 and take a note of parrent node, the time complexity should be O(nlogn + n) = O(nlogn) totally.

Using the array2, construct BST O(nlogn + nlogn).
Sorry:)

package org.nrec.probs;

import java.util.Comparator;

public class MNodeI implements Comparator<MNode>{


@Override
public int compare(MNode arg0, MNode arg1) {
if(arg0.i > arg1.i){
return 1;
}else if(arg0.i < arg1.i){
return -1;
}
return 0;
}

}

package org.nrec.probs;

import java.util.Comparator;

public class MNodeJ implements Comparator<MNode>{


	@Override
	public int compare(MNode arg0, MNode arg1) {
		if(arg0.j > arg1.j){
			return -1;
		}else if(arg0.j < arg1.j){
			return 1;
		} 
		return 0;
	}
	
}

package org.nrec.probs;

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Stack;

public class MNode {
	
	public MNode(int i ,int j){
		this.i = i;
		this.j = j;
	}
	
	public MNode(){
	}
	

	public MNode(MNode temp){
		this.i = temp.i;
		this.j = temp.j;
	}
	
	public String toString(){
		return  " i :: " + i  + " j :: " + j;
	}
	
	
	public int i;
	public int j; 
	
	MNode left;
	MNode right;
	
	public MNode createBSTHeap(List<MNode> numbers){
		if(numbers == null || numbers.size() == 0){
			return null;
		}
		Collections.sort(numbers,new MNodeJ());
		MNode temp = numbers.get(0);
		Collections.sort(numbers,new MNodeI());
		int index = numbers.indexOf(temp);
		System.out.println("index :: "+index);
		System.out.println("temp :: "+temp);
		System.out.println("Total ::  "+numbers);

		List<MNode> leftSubTree = null; 
		try{
			leftSubTree = (List<MNode>) numbers.subList(0, index);

		}catch(Exception e){
			leftSubTree  = null;
		}
		List<MNode> rightSubTree =  null;
		
		try{
			rightSubTree = (List<MNode>) numbers.subList(index+1, numbers.size());
		}catch(Exception e){
			rightSubTree = null;
		}
		MNode root = new MNode(temp);
		System.out.println("this node :: "+ root);
		System.out.println("leftSubTree "+leftSubTree);
		System.out.println("rightSubTree "+rightSubTree);
		
		if(leftSubTree != null)
			root.left = createBSTHeap(leftSubTree);
		else root.left = null;
		
		
		
		if(rightSubTree != null)
			root.right = createBSTHeap(rightSubTree);
		else
			root.right = null;
		

		System.out.println("Returning back \n node :: "+ root);
		System.out.println("Left :: "+root.left);
		System.out.println("Right :: "+root.right);
		return root;
	}
	
	public void preorderI(MNode root){
		if(root!=null){
			preorderI(root.left);
			System.out.print(root.i+",");
			preorderI(root.right);
		}
	}
	
	public void preorderJ(MNode root){
		if(root!=null){
			preorderJ(root.left);
			System.out.print(root.j+",");
			preorderJ(root.right);
		}
	}
	
	public static void main(String[] args){
//		(12,6) (18,25) (19,10) (17,5) (19,10) 
		MNode mnode1 = new MNode(12,6);
		MNode mnode2 = new MNode(18,25);
		MNode mnode3 = new MNode(19,10);
		MNode mnode4 = new MNode(17,5);
		MNode mnode5 = new MNode(19,10);
		List<MNode>  list = new ArrayList<MNode>();
		list.add(mnode1);
		list.add(mnode2);
		list.add(mnode3);
		list.add(mnode4);
		list.add(mnode5);
		MNode mnode = new MNode();
		MNode root = mnode.createBSTHeap(list);
		System.out.println(""+root.left);
		System.out.println(""+root.right);

		mnode.preorderI(root);
		System.out.println("");
		mnode.preorderJ(root);
	}
	

}

The traversal is inorder .... although by mistake I have named it as preorder !!!

Figure out the root node and then recursively keep feeling Left tree and right tree.
1. Root node: Node with minimum j value: Heap property.
2. Left node, Right node: You can always find a unique node satisfying both BST and heap properties.

Complexity: O(N^2)

@JuvN : Excellent solution man. Would just like to ask one thing..since it is a heap, which is always balanced, so height of tree will always be log n. Therefore, shouldn,t the worst case complexity be O(nlog n) instead of O(n^2)?

Why not build the b-tree one node at a time. Find the height the new node should be at, then insert it toe the left or right as appropriate.

At any point in time, you are comparing 2 nodes. The one you want to place (P) and a Node in the tree (T). Each node has a search and heap value (P.i, P.j, T.i, T.j)

Recursively traverse down the tree, going left and right based on P.i vs T.i, until you find a T.j that is less than P.j. Now that you have the appropriate height, set T.parent = P (left or right, based on a comparison with parents.i) and, based on P.i vs T.i, set P.left or P.right = T.

Be sure to check the boundaries (No tree exists yet; T is the first node in the tree and P must be placed above it; P must become a leaf node on the left or right of T)


semi-pseudo code:

compareAndPlace (P, T, parent)
  if !P             // Bad placement parameter
    throw

  if !T             // No tree exists
    if parent       // Parent must be null if T is null
      throw
    else            // !parent, placement node is the new tree
      return P

  if P.j < T.j      // P should be lower in the heap
    if P.i < T.i    // P should be left of T
      if T.left     // There is a left hand sub tree
        compareAndPlace(P, T.left, T)
      else          // there is no left node for the present tree node
        T.left = P
    else            // if P.i > T.i; P should be right of T
      if T.right    // There is a right subtree
        compareAndPlace(P, T.right, T)
      else          // There is no right node for the present tree node
        T.right = P
    return T
  else              // P.j > T.j, T should be below P
    if T.i < P.i    // T should be to the left of P
      P.left = T
    else            // T.i > P.i, T should be to the right of P
      P.right = T

    if parent
      if P.i < parent.i   // P should be to the left of parent
        parent.left = P
      else                // P.i > parent.i, P should be to the right of parent
        parent.right = P
      return parent       // * See note
    else                  // No parent, we are at the top of the tree
      return P

* The "return parent" line will only be reached if we have already traversed some distance down the tree. Thus, we are already in recursion and the returned result will be ignored.

My formatting was lost. Trying again:

compareAndPlace (P, T, parent)
{
  if  !P             // Bad placement parameter
    throw

  if !T             // No tree exists
  {
    if parent       // Parent must be null if T is null
      throw
    else            // !parent, placement node is the new tree
      return P
  }

  if P.j < T.j      // P should be lower in the heap
  {
    if P.i < T.i    // P should be left of T
    {
      if T.left     // There is a left hand sub tree
        compareAndPlace(P, T.left, T)
      else          // there is no left node for the present tree node
        T.left = P
    }
    else            // if P.i > T.i, P should be right of T
    {
      if T.right    // There is a right subtree
        compareAndPlace(P, T.right, T)
      else          // There is no right node for the present tree node
        T.right = P
    }
    return T
  }
  else              // P.j > T.j, T should be below P
  {
    if T.i < P.i    // T should be to the left of P
      P.left = T
    else            // T.i > P.i, T should be to the right of P
      P.right = T

    if parent
    {
      if P.i < parent.i   // P should be to the left of parent
        parent.left = P
      else                // P.i > parent.i, P should be to the right of parent
        parent.right = P
      return parent       // * See note
    }
    else                  // No parent, we are at the top of the tree
      return P
  }
}

Darn it:

"if !T" should be indented with 2 spaces
"if P.j < T.j" should be indented with 2 spaces
"if parent" should be indented with 4 spaces

TREAP

Node * createTree(Node arr[], int low ,int high)
  {  
      if(low > high) return;
       else
       {
       index = findIndexOfMaxJValue(arr);
       Node *root = malloc(arr[index]);
       root->left = createTree( arr, low, index-1);
       root->right = createTree( arr, index+1, high);
      return root;
  }
}

1. Sort the Nodes according to J. O(nlogn)
2. Get the min (j) guy from the lot, put it as root.
2. get the 2nd guy, and see according to i that it should go on left or right
and so on ..