fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class BinarySearchTree {
  8. public Node root;
  9. static class Node
  10. {
  11.     int data;
  12.     Node right;
  13.     Node left;
  14.  
  15.     public Node(int data)
  16.     {
  17.         this.data=data;
  18.         this.right=null;
  19.         this.left=null;
  20.     }
  21. }
  22.  
  23. public void insert(int data)
  24. {   
  25.     root=treeInsert(root,data);     
  26. }
  27.  
  28. public Node treeInsert(Node root,int data)
  29. {
  30.     if(root==null)
  31.         {
  32.         root=new Node(data);            
  33.         return root;
  34.         }
  35.  
  36.     if(data >= root.data)
  37.         root.right= treeInsert(root.right,data);
  38.     else 
  39.         root.left= treeInsert(root.left,data);
  40.  
  41.     return root;
  42. }
  43.  
  44.  
  45.  
  46. public static void main(String[] args) {
  47.     // TODO Auto-generated method stub
  48.  
  49.     BinarySearchTree tree = new BinarySearchTree();
  50.  
  51.     /* Let us create following BST
  52.           50
  53.        /     \
  54.       30      70
  55.      /  \    /  \
  56.    20   40  60   80 */
  57.     tree.insert(50);
  58.     tree.insert(30);
  59.     tree.insert(20);
  60.     tree.insert(40);
  61.     tree.insert(70);
  62.     tree.insert(60);
  63.     tree.insert(80);
  64.     System.out.println("successor :"+tree.inOrderSuccessor(45));    
  65.     System.out.println("successor :"+tree.inOrderSuccessor(55));
  66.  
  67. }
  68.  
  69. private int inOrderSuccessor(int i) {
  70.  
  71.     Node successor=recursiveInOrderSuccessor(root,i);
  72.     if(successor!=null)
  73.     return successor.data;
  74.     else
  75.         return -1;      
  76. }
  77.  
  78. private Node recursiveInOrderSuccessor(Node root2,int i) {
  79.     if(root2 == null) return null;
  80.     Node successor = null, succ2 = null;
  81.     if(root2.data == i) {
  82.         successor = root2.right;
  83.         while(successor.left != null){
  84.             successor = successor.left;
  85.         }
  86.         return successor;
  87.     }
  88.  
  89.     if(root2.data > i){
  90.         successor = root2;
  91.         succ2 = recursiveInOrderSuccessor(root2.left, i);
  92.         if(succ2 != null && succ2.data < successor.data)
  93.             return succ2;
  94.         else
  95.             return successor;
  96.     }
  97.     else{
  98.         return recursiveInOrderSuccessor(root2.right, i);
  99.     }
  100. }
  101.  
  102. }
Success #stdin #stdout 0.04s 711168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
successor :50
successor :60
https://ideone.com/yLKC19
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!