fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5.  
  6. /* Name of the class has to be "Main" only if the class is public. */
  7.     class BinarySearchTree {
  8.         TreeNode mRoot = null;
  9.  
  10.         static private class TreeNode {
  11.             TreeNode(int value, TreeNode parent) {
  12.                 this.value = value;
  13.                 this.parent = parent;
  14.             }
  15.  
  16.             TreeNode parent, left, right;
  17.             int value;
  18.         }
  19.  
  20.         public TreeNode successor(TreeNode node) {
  21.             if (node == null)
  22.                 return node;
  23.  
  24.             if (node.right != null) {
  25.                 return leftMostNode(node.right);
  26.             }
  27.  
  28.             while (null != node.parent /* while we are not root */
  29.                     && node.parent.right == node) {
  30.  
  31.                 node = node.parent; // go one level up
  32.             }
  33.  
  34.             return node.parent;
  35.         }
  36.  
  37.         public static TreeNode leftMostNode(TreeNode node) {
  38.             if (null == node) {
  39.                 return null;
  40.             }
  41.  
  42.             while (null != node.left) {
  43.                 node = node.left;
  44.             }
  45.             return node;
  46.         }
  47.  
  48.         /** Search value in Tree need for Successor **/
  49.         public TreeNode search(int key) {
  50.             TreeNode node = mRoot;
  51.             while (node != null 
  52.                     && key != node.value) {
  53.  
  54.                 if (key < node.value) {
  55.                     node = node.left;
  56.                 } else if (key > node.value) {
  57.                     node = node.right;
  58.                 }
  59.             }
  60.             return node;
  61.         }
  62.  
  63.         /** Returns Successor of given value **/
  64.         public int getSuccessor(int val) {
  65.             TreeNode node;
  66.             if (null == (node = search(val))
  67.                     || (null == (node = successor(node)))) {
  68.                 // either val is not in BST, or it is the last value-> no
  69.                 // successor
  70.                 return -1;// error_code for instance;
  71.             }
  72.  
  73.             return node.value;
  74.         }
  75.  
  76.         public BinarySearchTree(int[] array) {
  77.             for (int elem : array) {
  78.                 add(elem);
  79.             }
  80.         }
  81.  
  82.         public void add(int value) {
  83.             if (mRoot == null) {
  84.                 mRoot = new TreeNode(value, null);
  85.             } else {
  86.                 insert(mRoot, value);
  87.             }
  88.         }
  89.  
  90.         void insert(TreeNode node, int value) {
  91.             if (node == null)
  92.                 return;
  93.  
  94.             if (value < node.value) {
  95.                 if (node.left == null) { // insert as the new left node
  96.                     node.left = new TreeNode(value, node);
  97.                 } else { // insert in the left subtree
  98.                     insert(node.left, value);
  99.                 }
  100.             } else { // value >= node.value
  101.                 if (node.right == null) {
  102.                     node.right = new TreeNode(value, node);
  103.                 } else {
  104.                     insert(node.right, value);
  105.                 }
  106.             }
  107.         }
  108.  
  109.         public static void main(String[] args) {
  110.  
  111.             BinarySearchTree bst = 
  112.                 new BinarySearchTree(new int[]{30, 10, 45, 38, 20, 50, 25, 33, 8, 12});
  113.  
  114.             int value = 8; // first one
  115.             while (value != -1) {
  116.                 System.out.println("next for " + value + " is " +
  117.                     (value = bst.getSuccessor(value)));
  118.             }
  119.         }
  120.     }
  121.  
  122.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
next for 8 is 10
next for 10 is 12
next for 12 is 20
next for 20 is 25
next for 25 is 30
next for 30 is 33
next for 33 is 38
next for 38 is 45
next for 45 is 50
next for 50 is -1
https://ideone.com/HpFU1A
language:
Java (HotSpot 12)
created:
10 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!