Max heap and BST in same structure

Problem

Some number pairs are given. Arrange the number pairs in the form of a binary tree in such a fashion so that the first numbers in each tuple is arranged in a max heap and the second number in each tuple is arranged in a binary search tree.

Each node of the binary tree will contain a tuple, when we look at the first number of each node the structure will look as a max heap, when we look at the second number of each node the structure will look as binary search tree.

Example

Input:

(2,15),(6,19),(3,22),(24,13),(29,19),(23,15),(15,25),(15,8)

Output:

  (29,19)
|
--------------------------------
| |
(24,13) (15,25)
| |
---------------- --------
| | |
(15,8) (23,15) (3,22)
|
   ----------
   | |
   (2,15) (6,19)

Solution

Suppose each node has two values named heapValue and treeValue. Among all the nodes we first try to find the highest heapValue. This node will have to be the root of the tree for making it a max heap. Now we look at the treeValue of this node. All the nodes having lesser tree value than this will go to the left subtree and rest will go to the right subtree. Which can be built recursively.

Code

import java.util.ArrayList;
import java.util.List;


public class MaxHeapAndBinarySearchTree
{
 public static void main(String[] args)
 {
  List < node > list = new ArrayList < node >();
  for (int i = 0; i < 10; ++i)
  {
   list.add(new Node((int) (30 * Math.random()),
     (int) (30 * Math.random())));
  }
  Node root=createHeapAndBST(list);
  printNice(root);
 }

 private static Node createHeapAndBST(List < node > list)
 {
  if(list.size()==0)
   return null;
  Node top=list.get(0);
  for(Node node:list)
  {
   if(node.heapValue>top.heapValue)
    top=node;
  }
  list.remove(top);
  List < node > leftList=new ArrayList < node >();
  List < node > rightList=new ArrayList < node >();
  for(Node node:list)
  {
   if(node.treeValue<=top.treeValue)
    leftList.add(node);
   else
    rightList.add(node);
  }
  top.left=createHeapAndBST(leftList);
  top.right=createHeapAndBST(rightList);
  return top;
 }

 static class Node
 {
  public Node left;
  public Node right;
  public int heapValue;
  public int treeValue;

  public Node(int heapValue, int treeValue)
  {
   this.heapValue = heapValue;
   this.treeValue = treeValue;
  }
 }

 public static void printNice(Node root)
 {
  if (root == null)
   return;
  else
  {
   System.out.print("(" + root.heapValue + "," + root.treeValue + ")");
   if (root.left != null)
   {
    System.out.print("L->[");
    printNice(root.left);
    System.out.print("]");
   }
   if (root.right != null)
   {
    System.out.print("R->[");
    printNice(root.right);
    System.out.print("]");
   }
  }
 }
}

Index