// Binary Search Trees in C++
//   (translated from a Java program)
#include <iostream.h>
#include <stdlib.h>
class TreeNode {
public:
   TreeNode *left;  // pointer to left child
   int data;       // data item
   TreeNode *right; // pointer to right child
   // Constructor: tree with one node
   TreeNode (int d = 0) {
      data = d;
      left = right = 0;
   }
   // insert:  ignores duplicates
   void insert (int d) {
      if (d < data) {
         if (left == 0) left = new TreeNode(d);
         else left -> insert(d);
      }
      else if (d > data) {
         if (right == 0) right = new TreeNode(d);
         else right -> insert(d);
      }
   }
};
// Tree: uses TreeNode class
class Tree {
   TreeNode *root;
public:
   Tree() {root = 0;} // empty tree
   void insertNode (int d) {
      if (root == 0) root = new TreeNode(d);
      else root -> insert(d);
   }
   void inorderTrav() {inorderT(root);}
   void inorderT(TreeNode *node) {
      if (node == 0) return;
      inorderT(node -> left);
      cout << node -> data << " ";
      inorderT(node -> right);
   }
};
// main: test the Tree and TreeNode classes

int main () {
   Tree *tree = new Tree(); // empty tree
   int intVal;
   // insert 10 random ints
   cout << "Inserting the values: ";
   for (int i = 1; i <= 10; i++) {
      intVal = (int) (drand48()*100);
      cout << intVal << " ";
      tree -> insertNode(intVal);
   }
   cout << "\nInorder Traversal: ";
   tree -> inorderTrav();
   cout << "\n";
}

// Binary Search Trees in Java
//   (adapted from Deitel & Deitel, Chapter 17)
import java.util.*;

class TreeNode {

   public TreeNode left;  // ref to left child
   public int data;       // data item
   public TreeNode right; // ref to right child
   // Constructor: tree with one node
   public TreeNode (int d) {
      data = d;
      left = right = null;
   }
   // insert:  ignores duplicates
   public void insert (int d) {
      if (d < data) {
         if (left == null) left = new TreeNode(d);
         else left.insert(d);
      }
      else if (d > data) {
         if (right == null) right = new TreeNode(d);
         else right.insert(d);
      }
   }
}
// Tree: uses TreeNode class
class Tree {
   private TreeNode root;

   public Tree() {root = null;} // empty tree
   public void insertNode (int d) {
      if (root == null) root = new TreeNode(d);
      else root.insert(d);
   }
   public void inorderTrav() {inorderT(root);}
   public void inorderT(TreeNode node) {
      if (node == null) return;
      inorderT(node.left);
      System.out.print(node.data + " ");
      inorderT(node.right);
   }
}
// TreeTest: test the Tree and TreeNode classes
public class TreeTestS {
   public static void main (String args[]) {
      Tree tree = new Tree(); // empty tree
      int intVal;
      // insert 10 random ints
      System.out.print("Inserting the values: ");
      for (int i = 1; i <= 10; i++) {
         intVal = (int) (Math.random()*100);
         System.out.print(intVal + " ");
         tree.insertNode(intVal);
      }
      System.out.print("\nInorder Traversal: ");
      tree.inorderTrav();
      System.out.println();
   }
}