nearestRightKey.java

package com.thealgorithms.datastructures.trees;

import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;

final class NearestRightKey {
 private NearestRightKey() {
 }

 public static void main(String[] args) {
 NRKTree root = buildTree();
 Scanner sc = new Scanner(System.in);
 System.out.print("Enter first number: ");
 int inputX0 = sc.nextInt();
 int toPrint = nearestRightKey(root, inputX0);
 System.out.println("Key: " + toPrint);
 sc.close();
 }

 public static NRKTree buildTree() {
 int randomX = ThreadLocalRandom.current().nextInt(0, 100 + 1);
 NRKTree root = new NRKTree(null, null, randomX);

 for (int i = 0; i < 1000; i++) {
 randomX = ThreadLocalRandom.current().nextInt(0, 100 + 1);
 root = root.insertKey(root, randomX);
 }

 return root;
 }

 public static int nearestRightKey(NRKTree root, int x0) {
 // Check whether tree is empty
 if (root == null) {
 return 0;
 } else {
 if (root.data - x0 > 0) {
 // Go left
 int temp = nearestRightKey(root.left, x0);
 if (temp == 0) {
 return root.data;
 }
 return temp;
 } else {
 // Go right
 return nearestRightKey(root.right, x0);
 }
 }
 }
}

class NRKTree {

 public NRKTree left;
 public NRKTree right;
 public int data;

 NRKTree(int x) {
 this.left = null;
 this.right = null;
 this.data = x;
 }

 NRKTree(NRKTree right, NRKTree left, int x) {
 this.left = left;
 this.right = right;
 this.data = x;
 }

 public NRKTree insertKey(NRKTree current, int value) {
 if (current == null) {
 return new NRKTree(value);
 }

 if (value < current.data) {
 current.left = insertKey(current.left, value);
 } else if (value > current.data) {
 current.right = insertKey(current.right, value);
 }

 return current;
 }
}