class bnode {   
  String key;
  bnode left;
  bnode right;
  bnode() {           
    key = null;
    left = null;
    right = null;
  }
  bnode(String key) {
    this.key = key;
    left = null;
    right = null;
  }
};
class BinarySearchTree {                
  bnode root;
  BinarySearchTree() {
    root = null;
  }
  void put(String key) {
    bnode current = root;
    bnode prev = current;
    if (root == null) {
      root = new bnode(key);
    }
    else {
      boolean insert = false;
      while (insert == false) {
        prev = current;
        if (key.compareTo(current.key) < 0) {
          if (current.left == null) {
            current.left = new bnode(key);
            insert = true;
          }
          current = current.left;
        }
        else {
          if (current.right == null) {
            current.right = new bnode(key);
            insert = true;
          }
          current = current.right;
        }
      }
    }
  }
  boolean delete(String key) {        
    boolean deleted = true;
    bnode current = root;
    bnode prev = current;
    while (current != null) {
      if (key.compareTo(current.key) > 0) {
        prev = current;
        current = current.right;
      }
      else if (key.compareTo(current.key) < 0) {
        prev = current;
        current = current.left;
      }
      else if (key.compareTo(current.key) == 0) {
        deleted = false;
        break;
      }
    }
    if (check(current) == 0) {
      if (current.key.compareTo(prev.key) > 0) {
        prev.right = null;
      }
      else {
        prev.left = null;
      }
    }
    else if (check(current) == 1) {

      if (current.key.compareTo(prev.key) > 0) {
        if (current.left != null) {
          prev.right = current.left;
        }
        else {
          prev.right = current.right;
        }
      }
      else {
        if (current.left != null) {
          prev.left = current.left;
        }
        else {
          prev.left = current.right;
        }
      }
    }
    else if (check(current) == 2) {
      bnode temp = inord(current);
      if (current == root) {
        root.key = temp.key;
      }
      else {
        if (current.key.compareTo(prev.key) > 0) {
          prev.right.key = temp.key;
        }
        else {
          prev.left.key = temp.key;
        }
      }
    }
    return deleted;
  }
  bnode inord(bnode a) {                    
    int t = 0;
    bnode ret, prev = new bnode();
    prev = a;
    a = a.right;
    while (a.left != null) {
      prev = a;
      a = a.left;
      t = 1;
    }
    ret = a;
    if (t == 0) {
      prev.right = null;
    }
    else {
      prev.left = null;
    }
    a = null;
    return ret;
  }
  int check(bnode a) { 
    int ret;
    if ( (a.left != null) && (a.right != null)) {
      ret = 2;
    }
    else if ( (a.left == null) && (a.right == null)) {
      ret = 0;
    }
    else {
      ret = 1;
    }
    return ret;
  }
  void printIn(bnode oot) {                  
    if (oot.left != null) {
      printIn(oot.left);
    }
    System.out.println("--------" + oot.key + "----------");
    if (oot.right != null) {
      printIn(oot.right);
    }
  }
  public static void main(String[] args) {
    BinarySearchTree a = new BinarySearchTree();
    String names[]={"A","B","C","D"};
    for(int i=0;i<names.length;i++){
        a.put(names[i]);
    }
    a.printIn(a.root);
  }
}

import java.util.*;

    class TNode{
    int number;
    TNode parent;
    TNode leftChild;
    TNode rightChild;
    }
    public class BinarySearchTree{

    public TNode root = null; 
    TNode currentNode = root;

    public boolean IsEmpty(){
    if(root == null)
    return true;
    return false;
    }

    TNode create(int number){
    TNode node = new TNode();
    node.number = number;
    node.parent = null;
    node.leftChild = null;
    node.rightChild = null;
    return node;
    }

    public void insert(int number){
    currentNode = add (root,number);
    if(IsEmpty() == true && currentNode != null)
    root = currentNode;
    currentNode = root;
    }

    TNode add(TNode node, int number){
    if(node == null){
    node = create(number);
    return node;
    }
    else if(number < node.number){
    if(node.leftChild != null)
    add(node.leftChild,number);
    else
    node.leftChild = create(number);
    }
    else if(number >= node.number){
    if(node.rightChild != null)
    add(node.rightChild,number);
    else
    node.rightChild = create(number);
    }
    return null;
    }

    public void find(int number){
    IsEmpty();
    currentNode = find(root, number);

    System.out.println("Search returned Node: " + currentNode.number);
    System.out.println("Node's left child: " + currentNode.leftChild);
    System.out.println("Node's right child: " + currentNode.rightChild);
    }
    TNode find(TNode currentNode, int number){
    while(currentNode.number != number && currentNode != null){
    if(number < currentNode.number){
    currentNode = currentNode.leftChild;
    }
    else if(number > currentNode.number){
    currentNode = currentNode.rightChild;
    }
    else{
    currentNode = currentNode.rightChild;
    }
    }
    return currentNode;
    }
    public TNode getRoot(){
        return root;
    }
    private void display(TNode input){
    if(input == null){
    return;
    }
    display(input.leftChild);
    System.out.println(input.number);
    display(input.rightChild);
    }
    public static void main(String[] args){
    BinarySearchTree RBT = new BinarySearchTree();
    Scanner console = new Scanner(System.in);
    System.out.println("How many numbers would you like to enter into the Red Black Tree?");
    int k = console.nextInt();
    int inputarray[] = new int[k];
    for(int i=0; i< k; i++){
    System.out.println("Please enter the " + (i+1)+ " number: ");
    inputarray[i]= console.nextInt();
    }
    System.out.println("\n\n****Display Start****");
    for(int i=0; i<k; i++){
    RBT.insert(inputarray[i]);
    }
    RBT.display(RBT.getRoot());
    }
     }