Binary search tree implementation using java

Definition: A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.

(Binary search trees main operations - Searching, Insertion, Deletion, Traversaland  Verification)

1. public class BST<Key extends Comparable<Key>, Value>
2. {
3. private class Node
4. {
5. private Key key; // key
6. private Value val; // associated value
7. private Node left, right; // links to subtrees
8. private int N; // nodes in subtree
9. public Node(Key key, Value val, int N)
10. { this.key = key;
11.  this.val = val; 
12.  this.N = N;
13.  }
14. }
15. private Node root; // root of node of BST
16. 
    
17. public int size() //return size of BST
18. { return size(root); 
19. }
20. private int size(Node x)
21. {
22. if (x == null) return 0;
23. else return x.N;
24. }
25. public Value get(Key key)
26. { return get(root, key); }
27. private Value get(Node x, Key key)
28. { // Return value associated with key in the subtree rooted at x;
29. // return null if key not present in subtree rooted at x.
30. if (x == null) return null;
31. int cmp = key.compareTo(x.key);
32. if (cmp < 0) return get(x.left, key);
33. else if (cmp > 0) return get(x.right, key);
34. else return x.val;
35. }
36. public void insert(Key key, Value val)
37. { // Search for key. Update value if found; grow table if new.
38. root = insert(root, key, val);
39. }
40. private Node insert(Node x, Key key, Value val)
41. {
42. // Change key’s value to val if key in subtree rooted at x.
43. // Otherwise, add new node to subtree associating key with val.
44. if (x == null) return new Node(key, val, 1);
45. int cmp = key.compareTo(x.key);
46. if (cmp < 0) x.left = insert(x.left, key, val);
47. else if (cmp > 0) x.right = insert(x.right, key, val);
48. else x.val = val;
49. x.N = size(x.left) + size(x.right) + 1;
50. return x;
51. }
52. //chacking if a tree is binary search tree or not
53. bool isBST(Node node, int minKey, int maxKey) {
54.     if(node == NULL) return true;
55.     if(node.key < minKey || node.key > maxKey) return false;
56.     
57.     return isBST(node.left, minKey, node.key) && isBST(node.right, node.key, maxKey);
58. }
59. }

Example  :

      Node child1 = new Node(1, 1, 0);
   insert(child1, 1, 1);