In this lab, you will implement a few methods for Binary Search Tree $($BST$).$ You are given the class for the Tree node that supports generic types. As we demonstrated in the class discussion, you will add the following methods. We demonstrated how to implement the following methods.

$*$ Insert: insert a $($key$,$ value$)$ pair in the Binary Search Tree

$*$ Get: returns the value of a given key.

$*$ Inorder traversal: prints the $($key$,$ value$)$ pair from the left subtree, root, and right subtree.

$//$ Insert key$-$value pairs in BST$,$ if a key already exists update the value

public void insert$($Key key, Value value$)\{$

$//$ Implement

$\}$

$//$ Search BST for a given key

public Value get$($Key key$)\{$

$//$ Implement search for a given key

return null;

$\}$

public void inorder$($Node root$)\{$

$//$ Implement Inorder Traversal

$\}$

import java.util.Scanner;

public class BinarySearchTree, Value$>\{$

private Node root; $//$ root of binary search tree

class Node $\{$

private Key key; $//$ sorted by key

private Value value; $//$ data stored in the node

private Node left, right; $//$ pointers to left and right subtrees

private int size; $//$ number of nodes in subtree

public Node$($Key k$,$ Value v$)\{$

this.key $=$ k;

this.value $=$ v;

$\}$

$\}$

$//$ Insert key$-$value pairs in BST$,$ if a key already exists update the value

public void insert$($Key key, Value value$)\{$

$//$ Implement insertion of a key$-$value pair in a BST$.$

$\}$

$//$ Search BST for a given key

public Value get$($Key key$)\{$

$//$ Implement search for a given key

return null;

$\}$

public void inorder$($Node root$)\{$

$//$ Implement Inorder Traversal

$\}$

$//$ Bonus problem

public int size$()\{$

$//$ return the number of key$-$value pairs $($nodes$)$ in the BST

$\}$

public static void main$($String$[]$ args$)\{$

Scanner input $=$ new Scanner$($System$.$in$)$;

BinarySearchTree bst $=$ new BinarySearchTree$()$;

System.out.println$("$Enter key $($int$)$ and value $($string$)$ pairs $(-1$ to end$)")$;

System.out.println$("$For example $100$ Phoenix"$)$;

while$($input$.$hasNext$())\{$

int key $=$ input.nextInt$()$;

if$($key $==-1)$ break;

String value $=$ input.next$()$;

bst$.$insert$($key$,$ value$)$;

$\}$

System.out.println$("$Search for key: $20")$;

System.out.println$($bst$.$get$(20))$;

System.out.println$("$Inorder Traversal prints:"$)$;

bst$.$inorder$($bst$.$root$)$;

input.close$()$;

$\}$

$\}$