Write in Java ****----------------------------------------------------------**** Given a Binary Search Tree (BST) 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. A BST is a tree without duplicates. 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 int getDistance(int a, int b) Sample Input 7 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) DriverMain.java: DO NOT CHANGE ANYTHING IN THIS CODE FILE import java.util.*; import java.lang.*; import java.io.*; class DriverMain { public static void main(String args[]) { MyBST myTree = new MyBST(); Scanner input = new Scanner(System.in); int size = input.nextInt(); //Elements need to be added to max heap for(int i=0; i
- Write in Java
****----------------------------------------------------------****
Given a Binary Search Tree (BST) 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.
- A BST is a tree without duplicates.
- 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
int getDistance(int a, int b)
Sample Input
7
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)
DriverMain.java:
DO NOT CHANGE ANYTHING IN THIS CODE FILE
import java.util.*;
import java.lang.*;
import java.io.*;
class DriverMain {
public static void main(String args[]) {
MyBST myTree = new MyBST();
Scanner input = new Scanner(System.in);
int size = input.nextInt();
//Elements need to be added to max heap
for(int i=0; i<size; i++)
myTree.insert(Integer.parseInt(input.next()));
int a = input.nextInt();
int b = input.nextInt();
input.close();
System.out.println(myTree.getDistance(a, b));
}
}
MyBST.java:
import java.util.*;
import java.lang.*;
import java.io.*;
class MyBST {
TreeNode root;
//Find distance between 2 nodes with the given keys a and b
public int getDistance(int a, int b) {
//Write code here and you can add more methods
}
//*******Do NOT change the methods below*******
//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) return;
else 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 starting from root
public void print() {
Queue q = new LinkedList<TreeNode>();
if(root!=null)
q.add(root);
while(!q.isEmpty()) {
TreeNode current = (TreeNode) q.remove();
System.out.print(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;
}
}
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
