fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7.    static class Node
  8.    {
  9.       Integer key;
  10.       Node left, right;
  11.       Node(Integer key) { this.key = key; }
  12.    }
  13.  
  14.    static Integer specialKey = Integer.MAX_VALUE;
  15.  
  16.    static Integer successor(Integer target)
  17.    {
  18.       Integer successor = successor(root, target);
  19.       if (successor == specialKey)
  20.          return null;
  21.       return successor;
  22.    }
  23.    static Integer successor(Node current, Integer target)
  24.    {
  25.       if (current == null)
  26.          return null;
  27.       if (target.equals(current.key))
  28.          if (current.right != null)
  29.             return leftMost(current.right).key;
  30.          else
  31.             return specialKey;
  32.       else
  33.          if (target < current.key)
  34.          {
  35.             Integer s = successor(current.left, target);
  36.             if (s == specialKey)
  37.                return current.key;
  38.             else
  39.                return s;
  40.          }
  41.          else
  42.             return successor(current.right, target);
  43.    }
  44.  
  45.    static Node leftMost(Node current)
  46.    {
  47.       while (current.left != null)
  48.          current = current.left;
  49.       return current;
  50.    }
  51.  
  52.    static Node root;
  53.  
  54.    public static void main(String[] args)
  55.    {
  56.       // Constructs this tree:
  57.       //         6
  58.       //        / \
  59.       //       2   7
  60.       //      / \
  61.       //     1   4
  62.       //        / \
  63.       //       3   5
  64.  
  65.       root = new Node(6);
  66.       root.left = new Node(2);
  67.       root.left.left = new Node(1);
  68.       root.left.right = new Node(4);
  69.       root.left.right.left = new Node(3);
  70.       root.left.right.right = new Node(5);
  71.       root.right = new Node(7);
  72.       for (int i = 0; i <= 7; i++)
  73.          System.out.println("Successor of " + i + " is " + successor(i));
  74.    }
  75. }
Success #stdin #stdout 0.09s 27708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Successor of 0 is null
Successor of 1 is 2
Successor of 2 is 3
Successor of 3 is 4
Successor of 4 is 5
Successor of 5 is 6
Successor of 6 is 7
Successor of 7 is null
https://ideone.com/yTwFJ0
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!