document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. class BST_class {
  2.     //node class that defines BST node
  3.     class Node {
  4.         int key;
  5.         Node left, right;
  6.    
  7.         public Node(int data){
  8.             key = data;
  9.             left = right = null;
  10.         }
  11.     }
  12.     // BST root node
  13.     Node root;
  14.  
  15.    // Constructor for BST =>initial empty tree
  16.     BST_class(){
  17.         root = null;
  18.     }
  19.     //delete a node from BST
  20.     void deleteKey(int key) {
  21.         root = delete_Recursive(root, key);
  22.     }
  23.    
  24.     //recursive delete function
  25.     Node delete_Recursive(Node root, int key)  {
  26.         //tree is empty
  27.         if (root == null)  return root;
  28.    
  29.         //traverse the tree
  30.         if (key < root.key)     //traverse left subtree
  31.             root.left = delete_Recursive(root.left, key);
  32.         else if (key > root.key)  //traverse right subtree
  33.             root.right = delete_Recursive(root.right, key);
  34.         else  {
  35.             // node contains only one child
  36.             if (root.left == null)
  37.                 return root.right;
  38.             else if (root.right == null)
  39.                 return root.left;
  40.    
  41.             // node has two children;
  42.             //get inorder successor (min value in the right subtree)
  43.             root.key = minValue(root.right);
  44.    
  45.             // Delete the inorder successor
  46.             root.right = delete_Recursive(root.right, root.key);
  47.         }
  48.         return root;
  49.     }
  50.    
  51.     int minValue(Node root)  {
  52.         //initially minval = root
  53.         int minval = root.key;
  54.         //find minval
  55.         while (root.left != null)  {
  56.             minval = root.left.key;
  57.             root = root.left;
  58.         }
  59.         return minval;
  60.     }
  61.    
  62.     // insert a node in BST
  63.     void insert(int key)  {
  64.         root = insert_Recursive(root, key);
  65.     }
  66.    
  67.     //recursive insert function
  68.     Node insert_Recursive(Node root, int key) {
  69.           //tree is empty
  70.         if (root == null) {
  71.             root = new Node(key);
  72.             return root;
  73.         }
  74.         //traverse the tree
  75.         if (key < root.key)     //insert in the left subtree
  76.             root.left = insert_Recursive(root.left, key);
  77.         else if (key > root.key)    //insert in the right subtree
  78.             root.right = insert_Recursive(root.right, key);
  79.           // return pointer
  80.         return root;
  81.     }
  82.  
  83. // method for inorder traversal of BST
  84.     void inorder() {
  85.         inorder_Recursive(root);
  86.     }
  87.    
  88.     // recursively traverse the BST  
  89.     void inorder_Recursive(Node root) {
  90.         if (root != null) {
  91.             inorder_Recursive(root.left);
  92.             System.out.print(root.key + " ");
  93.             inorder_Recursive(root.right);
  94.         }
  95.     }
  96.      
  97.     boolean search(int key)  {
  98.         root = search_Recursive(root, key);
  99.         if (root!= null)
  100.             return true;
  101.         else
  102.             return false;
  103.     }
  104.    
  105.     //recursive insert function
  106.     Node search_Recursive(Node root, int key)  {
  107.         // Base Cases: root is null or key is present at root
  108.         if (root==null || root.key==key)
  109.             return root;
  110.         // val is greater than root\'s key
  111.         if (root.key > key)
  112.             return search_Recursive(root.left, key);
  113.         // val is less than root\'s key
  114.         return search_Recursive(root.right, key);
  115.     }
  116. }
  117.  
');