Binary Search Tree Part A: The code attached in this document is a sample code to demonstrate ins...
Binary Search Tree
Part A: The code attached in this document is a sample code to demonstrate insert operation in binary search tree. Please fill in the missing part for the insert method to make the program work. The expected output should be as follows.
20
30
40
50
60
70
80
Part B: Find Lowest Common Ancestor (LCA) of a Binary Search Tree. According to WikiPedia definition , The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). Write a function (Find Lowest Common Ancestor (LCA) of a Binary Search Tree) within the BinarySearchTree class in Part A and output test results.
Sample input: v: node 20, w: node 40. Expected output: node 30
Sample input: v: node 60, w: node 80. Expected output: node 70
Sample input: v: node 30, w: node 70. Expected output: node 50
// Java program to demonstrate insert operation in binary search tree
class BinarySearchTree {
/* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
Add your code here.
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// print inorder traversal of the BST
tree.inorder();
}
}
Homework Answers
PART A: BinarySearchTree.java:
// Java program to demonstrate insert operation in binary search tree
class BinarySearchTree {
/* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if(key < root.key)
root.left = insertRec(root.left, key);
else
if(key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// print inorder traversal of the BST
tree.inorder();
}
}
Output:
![File Microsoft Windows [Version 18.e.17763.379] c) 2018 Microsoft Corporation. All rights reserved. EPSON ONC:\Users Kotha Ru](http://img.homeworklib.com/images/c4e060fb-5d13-4a77-9847-e2090e6f9d4f.png?x-oss-process=image/resize,w_560)
PART B:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// Java program to demonstrate insert operation in binary search tree
class BinarySearchTree {
/* Class containing left and right child of current node and key keyue*/
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if(key < root.key)
root.left = insertRec(root.left, key);
else
if(key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
//Lowest Common Ancestor
private List<Integer> path1= new
ArrayList<>();
private List<Integer> path2= new
ArrayList<>();
//find the path from root node to given root of
the tree
int findLCA(int n1,int n2)
{
path1.clear();
path2.clear();
return
findLCAInternal(root,n1,n2);
}
private int findLCAInternal(Node root , int n1,
int n2)
{
if(!findpath(root,n1,path1)
|| !findpath(root,n2,path2))
{
System.out.println(path1.size() > 0 ? "n1 is present" : "n1 is
missing");
System.out.println(path2.size() > 0 ? "n2 is present" : "n2 is
missing");
return
-1;
}
int i;
for(i=0; i < path1.size()
&& i < path2.size(); i++)
{
//
System.out.println(path1.get(i) + " " + path2.get(i));
if
(!path1.get(i).equals(path2.get(i)))
break;
}
return path1.get(i-1);
}
//Finds the path from root node to given root of
the tree, stores the path in a vector path[],
//returns true if path exists , otherwsie
returns fals
private boolean findpath(Node root , int n,
List<Integer> path)
{
if(root==null)
{
return
false;
}
//stores this node. The node
will be removed if not in path from root to n.
path.add(root.key);
if(root.key == n) {
return
true;
}
if(root.left!= null
&& findpath(root.left , n , path)) {
return
true;
}
if(root.right!= null
&& findpath(root.right , n , path)) {
return
true;
}
// If not present in subtree
rooted with root, remove root from path[] and return false
path.remove(path.size()-1);
return false;
}
// Driver Program to test above functions
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// print inorder traversal of the BST
tree.inorder();
//reading
values and printing lowest common ancestor
Scanner
input= new Scanner(System.in);
System.out.println("Enter V and W nodes");
int
v=input.nextInt();
int
w=input.nextInt();
System.out.println("LCA(v,w): is " + tree.findLCA(v,w));
}
}
Output:
Add Answer to:
Binary Search Tree Part A: The code attached in this document is a sample code to demonstrate ins...
Can you take a look at my code that why the maxDepth function is not working?...
Can you take a look at my code that why the maxDepth function is not working? public class BinaryTree { class Node{ int key; Node left,right; public Node(int item) { key = item; left = right = null; } } Node root; public void BinaryTree(){ root = null; } void...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
In this assignment, you will add several methods to the Binary Search Tree. You should have compl...
In this assignment, you will add several methods to the Binary Search Tree. You should have completed the following three methods in the lab: public void insert(Key key, Value value) public Value get(Key key) public void inorder(Node root) For this assignment, you will implement the following: public void remove(Node root, Key key) public Key getMin(Node n) public Key getMax(Node n) public int height(Node n) The main method contains the statements to check whether your implementation works. You need to change...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Recall that in a binary search tree, at every node, all elements to the left of...
Recall that in a binary search tree, at every node, all elements to the left of the node have a smaller key, and all elements to the right of a node have a larger key. Write a program called that takes two parameters: a pointer to a binary search tree node, and an int parameter called min which will print all the elements bigger than the specified value, min. Your program should allow the user to enter data (integer) from...
C++ (Using Binary Search Trees) other methods will result in downvote Implement the binary search tree...
C++ (Using Binary Search Trees) other methods will result in downvote Implement the binary search tree methods (bst.cpp) for the binary search tree provided in the header file. Test your implementation with the included test. bst.h bst_test.cpp Note: Your implementation must correspond to declarations in the header file, and pass the test. Do not modify these two. I will compile your code against these. If the compilation fails, you will get down vote. bst.h #ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H #include <string>...
Question - modify the code below so that for a node, the value of every node...
Question - modify the code below so that for a node, the value of every node of its right subtree is less the node, and the value of each node of its left subtree is greater than the node. - create such a binary tree in the Main method, and call the following method: InOrder(Node theRoot), PreOrder(Node theRoot), PostOrder(Node theRoot), FindMin(), FindMax(), Find(int key) using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;...
C++ Binary Search Tree question. I heed help with the level 2 question please, as level...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
C++ Binary Search Tree question. I heed help with the level 2 question please, as level...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
using java to write,show me the output. please write some common. You CAN NOT use inbuild...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
Most questions answered within 3 hours.
-
2. Boris recently synthesized an explosive compound he named
Badenoughium. The molecular formula for Bdenoughium is...
asked 2 hours ago -
5. A car decelerate evenly from a velocity of 50mph until rest
in a distance of...
asked 2 hours ago -
IN HTML Programming
1. Write a script that inputs integers (one at a time) and
passes...
asked 2 hours ago -
A dentist uses a mirror to examine a tooth that is 0.75 cm in
front of...
asked 2 hours ago -
You set up a 100,000 line of credit for the business on 1/1/X8,
annual interest is...
asked 2 hours ago -
What is the measurement uncertainty of a pan balance? How did you
get that?
asked 2 hours ago -
Suppose four firms have market shares of 30%, 30%, 20% and 20%.
What is the Herfindahl-Hirschman...
asked 3 hours ago -
IBT Industrial Solutions produces forty units of rack and pinion
type steering gears during an eight...
asked 3 hours ago -
The Ksp for PbI2 is 9.8×10−9 . Will PbI2 precipitate if 2.5 mL
of 0.0025 M...
asked 3 hours ago -
- Write a Person Constructor that initializes `name` and
`age` from arguments.
- All instances of...
asked 3 hours ago -
What is the meaning of the statement: In acid-base catalysis,
acid catalysis involves partial proton transfer...
asked 3 hours ago -
Polo Publishers purchased a multi-color offset press with terms
of $65,000 down and a noninterest-bearing note...
asked 3 hours ago