Question
************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
************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!
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started