************IN JAVA******************

Given a Binary Search Tree and two keys in it. Implement the getDistance method to find the distance between two nodes with given keys, a and b.

We assume that both keys exist in BST.

Distance between two nodes is the minimum number of edges to be traversed to reach one node from other

// find the distance between two nodes with given two keys, a and b

public int getDistance(int a, int b)

Sample Input

5 2 12 1 3 9 21

3

9

5

/ \

2 12

/ \ / \

1 3 9 21

Sample Output

4

First line of the input is the BST elements

Second line is the first key

Third line is the secod key

The distance from a = 3 to b = 9 in the above BST is 4. (number of edges beween node a and b)

******************************************************************************

Here is the Main method, DO NOT ALTER.

******************************************************************************

import java.util.*; import java.lang.*; import java.io.*;

class DriverMain{

public static void main(String args[]){

Scanner input = new Scanner(System.in);

String str = input.nextLine();

int a = input.nextInt();

int b = input.nextInt();

input.close();

int[] arr = Arrays.stream(str.substring(0, str.length()).split("\\s"))

.map(String::trim).mapToInt(Integer::parseInt).toArray();

BST myTree = new BST();

for(int i = 0; i < arr.length; i++){

myTree.insert(arr[i]);

}

//myTree.breadthFirst();

System.out.println(myTree.getDistance(a, b));

}

}

***********************************************************************

Edit where it says WRITE CODE HERE

***********************************************************************

class BST {

TreeNode root;

// find the distance between two nodes with given keys a and b

public int getDistance(int a, int b){

//Write your code here

}

// insert method to add elements to BST

public void insert(int key){

TreeNode newNode = new TreeNode(key);

if(root == null){

root = newNode;

}else{

TreeNode current = root;

TreeNode parent;

while(true){

parent = current;

if(key < current.element){

current = current.left;

if(current == null){

parent.left = newNode;

return;

}

}else{

current = current.right;

if(current == null){

parent.right = newNode;

return;

}

}

}

}

}

//Print the elements of the BST level by level staring from root

public void breadthFirst(){

Queue q = new LinkedList();

if(root!= null)

q.add(root);

while(!q.isEmpty()){

TreeNode current = (TreeNode) q.remove();

System.out.println(current.element);

if(current.left != null)

q.add(current.left);

if(current.right != null)

q.add(current.right);

}

}

private class TreeNode {

int element;

TreeNode left;

TreeNode right;

public TreeNode(){}

public TreeNode(int e){

this.element = e;

}

}

}

***************************************************************

Any comments in your coding would be much appreciated!