Java Program to Implement Cartesian Tree

This is a Java Program to implement Cartesian Tree. A Cartesian tree is a binary tree derived from a sequence of numbers. It can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Introduced by Vuillemin (1980) in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence.

Here is the source code of the Java program to implement Cartesian Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *  Java Program to Implement Cartesian Tree
  3.  */
  4.  
  5.  import java.util.Scanner;
  6.  
  7.  /* Class CTNode */
  8.  class CTNode
  9.  {    
  10.      CTNode left, right;
  11.      int value;
  12.  
  13.      /* Constructor */
  14.      public CTNode()
  15.      {
  16.          left = null;
  17.          right = null;
  18.          value = 0;         
  19.      }     
  20.  }
  21.  
  22.  /* Class CartesianTree */
  23.  class CartesianTree
  24.  {
  25.      private CTNode root;
  26.  
  27.      /* Constructor */
  28.      public CartesianTree(int[] data)
  29.      {
  30.          root = build(data);
  31.      }
  32.      /* Function to build Cartesian Tree from array */
  33.      public CTNode build(int[] data) 
  34.      {
  35.         if (data == null || data.length == 0) 
  36.             return null;
  37.         return build(data, 0, data.length - 1);
  38.      }
  39.      /* Function to build Cartesian Tree from array */
  40.      private CTNode build(int[] data, int start, int end) 
  41.      {
  42.          if (end < start) 
  43.              return null;
  44.          int min = Integer.MAX_VALUE;
  45.          int minIndex = -1;        
  46.          for (int i = start; i <= end; i++) 
  47.          {
  48.              if (data[i] < min) 
  49.              {
  50.                  min = data[i];
  51.                  minIndex = i;
  52.              }
  53.          }        
  54.          CTNode node = new CTNode();
  55.          node.value = min;        
  56.          node.left = build(data, start, minIndex - 1);
  57.          node.right = build(data, minIndex + 1, end);        
  58.          return node;
  59.      }      
  60.      /* Function to check if tree is empty */
  61.      public boolean isEmpty()
  62.      {
  63.          return root == null;
  64.      }
  65.      /* Functions to count number of nodes */
  66.      public int countNodes()
  67.      {
  68.          return countNodes(root);
  69.      }
  70.      private int countNodes(CTNode r)
  71.      {
  72.          if (r == null)
  73.              return 0;
  74.          else
  75.          {
  76.              int l = 1;
  77.              l += countNodes(r.left);
  78.              l += countNodes(r.right);
  79.              return l;
  80.          }
  81.      }
  82.      /* Function for inorder traversal */
  83.      public void inorder()
  84.      {
  85.          inorder(root);
  86.      }
  87.      private void inorder(CTNode r)
  88.      {
  89.          if (r != null)
  90.          {
  91.              inorder(r.left);
  92.              System.out.print(r.value +" ");
  93.              inorder(r.right);
  94.          }
  95.      }
  96.      /* Function for preorder traversal */
  97.      public void preorder()
  98.      {
  99.          preorder(root);
  100.      }
  101.      private void preorder(CTNode r)
  102.      {
  103.          if (r != null)
  104.          {
  105.              System.out.print(r.value +" ");
  106.              preorder(r.left);             
  107.              preorder(r.right);
  108.          }
  109.      }
  110.      /* Function for postorder traversal */
  111.      public void postorder()
  112.      {
  113.          postorder(root);
  114.      }
  115.      private void postorder(CTNode r)
  116.      {
  117.          if (r != null)
  118.          {
  119.              postorder(r.left);             
  120.              postorder(r.right);
  121.              System.out.print(r.value +" ");
  122.          }
  123.      }         
  124.  }
  125.  
  126.  /* Class CartesianTreeTest */
  127.  public class CartesianTreeTest
  128.  {
  129.      public static void main(String[] args)
  130.      {            
  131.         Scanner scan = new Scanner(System.in);
  132.         System.out.println("Cartesian Tree Test\n");
  133.         System.out.println("Enter number of integer values");
  134.         int N = scan.nextInt();
  135.         int arr[] = new int[N];
  136.         System.out.println("\nEnter "+ N +" integer values");
  137.         for (int i = 0; i < N; i++)
  138.             arr[i] = scan.nextInt();
  139.         /* Make cartesian tree from given array */         
  140.         CartesianTree ct = new CartesianTree(arr);
  141.         /* Print tree details */
  142.         System.out.println("\nTree Details :");
  143.         System.out.println("Empty status - "+ ct.isEmpty());
  144.         System.out.println("No of nodes - "+ ct.countNodes());
  145.         System.out.print("Post order : ");
  146.         ct.postorder();
  147.         System.out.print("\nPre order : ");
  148.         ct.preorder();
  149.         System.out.print("\nIn order : ");
  150.         ct.inorder();
  151.         System.out.println();
  152.      }
  153.  }

Cartesian Tree Test
 
Enter number of integer values
11
 
Enter 11 integer values
9 3 7 1 8 12 10 20 15 18 5
 
Tree Details :
Empty status - false
No of nodes - 11
Post order : 9 7 3 12 20 18 15 10 8 5 1
Pre order : 1 3 9 7 5 8 10 12 15 20 18
In order : 9 3 7 1 8 12 10 20 15 18 5
 
 
 
Cartesian Tree Test
 
Enter number of integer values
0
 
Enter 0 integer values
 
Tree Details :
Empty status - true
No of nodes - 0
Post order :
Pre order :
In order :

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.