We need to write a method that, given a key as an argument, returns the next...
We need to write a method that, given a key as an argument, returns the next in order key found in the binary search tree. If the key given as an argument is not found, the method should still return the next in order key. If the binary tree is empty or all the stored keys are smaller than the argument, then the return value should be empty. For example, using a collection of {10,13,52,67,68,83} stored in the binary search tree: An input of 13 results in 52 An input of 67 results in 68 An input of 55 results in 67 An input of 5 results in 10 An input of 83 results in Optional.empty An input of 100 results in Optional.empty Any input on an empty binary tree results in Optional.empty Both the in order successor and predecessor algorithms have many applications. As an example, think about if you had to keep a scoreboard at some sports event where you only want to show the first three runners. If you keep your data in a binary search tree, you can find the maximum key and then work out the next two predecessor nodes. The solution needs to have a runtime complexity of O(log n).
Programming language Java
Homework Answers
The required method is as follows:
// Define the method to find the successor of the
// given key.
public Optional<Integer> inOrderSuccessor(int value)
{
Node curr = this.root;
Node prev = this.root;
// Start the loop to traverse the tree
// and check if the value is found or not.
while (curr != null)
{
// If the value is found, break the loop.
if (value == curr.key)
{
break;
}
// Move to the left child if the value
// is less than the current value.
else if (value < curr.key)
{
prev = curr;
curr = curr.left;
}
// Move to the right child if the value
// is greater than the current value.
else
{
prev = curr;
curr = curr.right;
}
}
// If the node is not found, check the value
// of the previous node.
if (curr == null)
{
// Return the key of the previous node
// if is is greater than the value
// to search.
if (prev.key > value)
{
return Optional.of(prev.key);
}
// Otherwise, make the previous as the
// current node.
else
{
curr = prev;
}
}
// If the right child is not null,
// find the minimum value of the right sub tree.
if (curr.right != null)
{
curr = curr.right;
while (curr.left != null)
{
curr = curr.left;
}
return Optional.of(curr.key);
}
Node temp = this.root;
Node successor = null;
// Start the loop to traverse the tree.
while (temp != null)
{
// Move to the left child if the value
// is less than the current value.
if (value < temp.key)
{
successor = temp;
temp = temp.left;
}
// Move to the right child if the value
// is greater than the current value.
else if (value > temp.key)
{
temp = temp.right;
}
// Otherwise, break the loop.
else
{
break;
}
}
// Return the key of the successor node if the
// node is not null.
if (successor != null)
{
return Optional.of(successor.key);
}
// Otherwise, return Optional.empty.
return Optional.empty();
}
The running time of the above function is as follows:
- To find if the value is present in the tree or not, the function either goes to the left child or the right child, starting with the root node, until it reaches one of the leaf nodes.
- The average running time of the function is equal to O (log n), where n is the number of nodes in the tree.
- After the node is found, the next loop is used to find the in-order successor which also moves to either left or right child, starting with the root node, until it reaches one of the leaf nodes.
- The average running time of the function is equal to O (log n), where n is the number of nodes in the tree.
- Therefore, the total running time of the above function is O (log n) + O (log n) = O (log n).
The complete program to test the above method is as follows:
Program screenshots:
BST.java:
testBST.java:
Sample output:
Code to copy:
BST.java:
import java.util.*;
// Define the class BST.
public class BST
{
// Declare the root node.
private Node root;
// Define the class to create the
// node of the tree.
private static class Node
{
// Declare the public members of
// the class.
public final int key;
public Node left, right;
// Define the parameterized constructor
// to set the key.
public Node(int key)
{
this.key = key;
}
}
// Define the default constructor to set
// the root node to null.
BST()
{
root = null;
}
// Define the method to insert a value in
// the tree.
void insert(int value)
{
// Call the helper function to
// insert the value in the tree.
root = insert_helper(value, root);
}
// Define a helper function to insert a
// value in the tree.
Node insert_helper (int value, Node root)
{
// Create a new node with the given
// value if the current node is null.
if (root == null)
{
root = new Node(value);
return root;
}
// Call the method recursively with the
// left subtree if the value to be inserted
// is less than the value of the current node.
if (value < root.key)
{
root.left = insert_helper(value, root.left);
}
// Call the method recursively with the
// right subtree if the value to be inserted
// is greater than the value of the current node.
else if (value > root.key)
{
root.right = insert_helper(value, root.right);
}
// Return the root node.
return root;
}
// Define the method to print the inorder
// traversal of the tree.
void inorder()
{
// Call the helper function with the
// root node.
inorder_helper(root);
}
// Define the helper function to print the inorder
// traversal of the tree.
void inorder_helper(Node root)
{
// Check if the current node is null or not.
if (root != null)
{
// Call the method recursively with the
// left subtree.
inorder_helper(root.left);
// Print the value of the current node.
System.out.print(root.key + " ");
// Call the method recursively with the
// right subtree.
inorder_helper(root.right);
}
}
// Define the method to find the successor of the
// given key.
public Optional<Integer> inOrderSuccessor(int value)
{
Node curr = this.root;
Node prev = this.root;
// Start the loop to traverse the tree
// and check if the value is found or not.
while (curr != null)
{
// If the value is found, break the loop.
if (value == curr.key)
{
break;
}
// Move to the left child if the value
// is less than the current value.
else if (value < curr.key)
{
prev = curr;
curr = curr.left;
}
// Move to the right child if the value
// is greater than the current value.
else
{
prev = curr;
curr = curr.right;
}
}
// If the node is not found, check the value
// of the previous node.
if (curr == null)
{
// Return the key of the previous node
// if is is greater than the value
// to search.
if (prev.key > value)
{
return Optional.of(prev.key);
}
// Otherwise, make the previous as the
// current node.
else
{
curr = prev;
}
}
// If the right child is not null,
// find the minimum value of the right sub tree.
if (curr.right != null)
{
curr = curr.right;
while (curr.left != null)
{
curr = curr.left;
}
return Optional.of(curr.key);
}
Node temp = this.root;
Node successor = null;
// Start the loop to traverse the tree.
while (temp != null)
{
// Move to the left child if the value
// is less than the current value.
if (value < temp.key)
{
successor = temp;
temp = temp.left;
}
// Move to the right child if the value
// is greater than the current value.
else if (value > temp.key)
{
temp = temp.right;
}
// Otherwise, break the loop.
else
{
break;
}
}
// Return the key of the successor node if the
// node is not null.
if (successor != null)
{
return Optional.of(successor.key);
}
// Otherwise, return Optional.empty.
return Optional.empty();
}
}
testBST.java:
// Import the required packages.
import java.util.*;
// Define the class testBST.
class testBST
{
public static void main(String[] args)
{
// Create an object of the BST class.
BST bst1 = new BST();
// Insert values in the tree.
bst1.insert(67);
bst1.insert(52);
bst1.insert(68);
bst1.insert(10);
bst1.insert(83);
bst1.insert(13);
// Print the values in the tree.
System.out.print("Values in the tree (inorder):");
bst1.inorder();
System.out.println("\n");
Optional<Integer> successor;
// Call the method to find the inorder
// successor and display the result if the
// value is present. Otherwise, print the
// empty message.
System.out.print("Inorder of 13 = ");
successor = bst1.inOrderSuccessor(13);
if (successor.isPresent())
{
System.out.println(successor.get());
}
else
{
System.out.println(successor);
}
System.out.print("Inorder of 67 = ");
successor = bst1.inOrderSuccessor(67);
if (successor.isPresent())
{
System.out.println(successor.get());
}
else
{
System.out.println(successor);
}
System.out.print("Inorder of 55 = ");
successor = bst1.inOrderSuccessor(55);
if (successor.isPresent())
{
System.out.println(successor.get());
}
else
{
System.out.println(successor);
}
System.out.print("Inorder of 5 = ");
successor = bst1.inOrderSuccessor(5);
if (successor.isPresent())
{
System.out.println(successor.get());
}
else
{
System.out.println(successor);
}
System.out.print("Inorder of 83 = ");
successor = bst1.inOrderSuccessor(83);
if (successor.isPresent())
{
System.out.println(successor.get());
}
else
{
System.out.println(successor);
}
System.out.print("Inorder of 100 = ");
successor = bst1.inOrderSuccessor(100);
if (successor.isPresent())
{
System.out.println(successor.get());
}
else
{
System.out.println(successor);
}
}
}
Add Answer to:
We need to write a method that, given a key as an argument,
returns the next...
Scenario We need to write a method that, given a key as an argument, returns the...
Scenario We need to write a method that, given a key as an argument, returns the next in order key found in the binary search tree. If the key given as an argument is not found, the method should still return the next in order key. If the binary tree is empty or all the stored keys are smaller than the argument, then the return value should be empty. For example, using a collection of {10,13,52,67,68,83} stored in the binary...
Write a recursive function that returns the minimum key value in a binary search tree of...
Write a recursive function that returns the minimum key value in a binary search tree of distinct (positive) integers. Return -1 in case the tree is empty. (b) Write a recursive function that returns the predecessor of the key value k in a binary search tree of distinct (positive) integers. This is the key value that precedes k in an inorder traversal of the tree. If k does not exist, or if k has no predecessor, your function should return...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\ package Tree; public class BinaryTree { private TreeNode root; // head of the list //constructor - create an empty binary tree public BinaryTree() { root = null; } //isEmpty() - return true if tree is empty, false otherwise public boolean isEmpty() { return (root == null); } //deleteTree() - remove all items from tree public void deleteList() { root =...
Using the following implementation of Tree class Node { public int iData; // data item (key) public...
Using the following implementation of Tree class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child public void displayNode() // display ourself { System.out.print('{'); System.out.print(iData); System.out.print(", "); System.out.print(dData); System.out.print("} "); } } // end class Node //------------------------------------------------------------------ import java.io.IOException; import java.util.Stack; public class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; }...
Write a client method that returns a count of the number of nodes in a binary...
Write a client method that returns a count of the number of
nodes in a binary search tree that contain scores less than or
equal to a passed-in argument (parameter) value. The method header
is:
int countLowerScores (BinarySearchTree tree, int maxValue)
The BinarySearchTree contains these methods in the
picture.
public class BinarySearchTreecT> implements BSTInterfacecT> //reference to the root of this BST public BSTNode<T> root; public Comparator<T> comp: IIused for all comparisons public boolean found: / used by remove public BinarYSearchTree()...
Attention!!!!!!! I need python method!!!!!!!!! the part which need to edit is below: i nee...
attention!!!!!!! I need python method!!!!!!!!!
the part which need to edit is below: i need python
one!!!!!!!!!
the part below is interface for the range search tree which
don’t need to modify it.
Week 3: Working with a BST TODO: Implement a Binary Search Tree (Class Name: RangesizeTree) Choose one language fromJava or Python. Iin both languages,there is an empty main function in the Range Size Tree file. The main function is not tested, however, it is provided for you...
Write a function int levelSearch(Node* root, int key) that takes as input the root node of...
Write a function int levelSearch(Node* root, int key) that takes as input the root node of a Binary Search tree and a key. The function searches the key in the BST and returns the level of the found node. If the key is not found in the tree, return -1. The level starts at 0 for the root node and increases from top to bottom. We have defined the following node C++ Node class for you: class Node { public: ...
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...
I need help with this code, I'm stuck on it, please remember step 4, I'm very...
I need help with this code,
I'm stuck on it, please remember step 4, I'm very much stuck on
that part. It says something about putting how many times it
appears
Assignment #1: Sorting with Binary Search Tree Through this programming assignment, the students will learn to do the following: Know how to process command line arguments. 1 Perform basic file I/O. 2. Use structs, pointers, and strings. Use dynamic memory. 3. 4. This assignment asks you to sort the...
Add printRang method to BST.java that, given a low key value, and high key value, print...
Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys. (Both low key and high key do not have to be a key on the list). BST.java import java.lang.Comparable; /** Binary Search Tree implementation for Dictionary ADT */ class BST<Key extends Comparable<? super Key>, E> implements Dictionary<Key, E> { private BSTNode<Key,E> root; // Root of the BST int nodecount; //...
Write a recursive function that returns the minimum key value in a binary search tree of distinct (positive) integers. Return -1 in case the tree is empty. (b) Write a recursive function that returns the predecessor of the key value k in a binary search tree of distinct (positive) integers. This is the key value that precedes k in an inorder traversal of the tree. If k does not exist, or if k has no predecessor, your function should return...
Write a client method that returns a count of the number of
nodes in a binary search tree that contain scores less than or
equal to a passed-in argument (parameter) value. The method header
is:
int countLowerScores (BinarySearchTree tree, int maxValue)
The BinarySearchTree contains these methods in the
picture.
public class BinarySearchTreecT> implements BSTInterfacecT> //reference to the root of this BST public BSTNode<T> root; public Comparator<T> comp: IIused for all comparisons public boolean found: / used by remove public BinarYSearchTree()...
attention!!!!!!! I need python method!!!!!!!!!
the part which need to edit is below: i need python
one!!!!!!!!!
the part below is interface for the range search tree which
don’t need to modify it.
Week 3: Working with a BST TODO: Implement a Binary Search Tree (Class Name: RangesizeTree) Choose one language fromJava or Python. Iin both languages,there is an empty main function in the Range Size Tree file. The main function is not tested, however, it is provided for you...
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...
I need help with this code,
I'm stuck on it, please remember step 4, I'm very much stuck on
that part. It says something about putting how many times it
appears
Assignment #1: Sorting with Binary Search Tree Through this programming assignment, the students will learn to do the following: Know how to process command line arguments. 1 Perform basic file I/O. 2. Use structs, pointers, and strings. Use dynamic memory. 3. 4. This assignment asks you to sort the...
Most questions answered within 3 hours.
-
Calculate ΔE, if a system releases 66.3 kJof heat to its
surroundings while the surroundings do...
asked 30 seconds ago -
Find the center of mass of the Eath-moon
system given:
Radius of Earth = 6.37x10^6
Radius...
asked 1 minute ago -
Write a brief essay (300-500 words) that describes how a
country's economic growth can be measured...
asked 5 minutes ago -
Use Kepler's third law to show that the closer a planet is to
the Sun, the...
asked 12 minutes ago -
2) A car is traveling at 18 m/s on a horizontal highway.
(a.) If the coefficient...
asked 12 minutes ago -
Assignment Overview
In Part 1 of this assignment, you will write a main program and
several...
asked 12 minutes ago -
A person weighing 507 N stands in an elevator that decelerates
at a rate of 1.9...
asked 14 minutes ago -
DISCUSSION POST:
Identify a country with a recent change in its exchange rate
arrangement.
Describe its...
asked 17 minutes ago -
For the following reaction, 3.30 grams of phosphoric acid are
mixed with excess potassium hydroxide ....
asked 21 minutes ago -
40
1
363.9
40
1
501.4
40
2
448.2
40
2
914
40
3
532.2
40...
asked 24 minutes ago -
microsoft has a listed par value of $0.00000625 per share. if the
originally issued shares had...
asked 30 minutes ago -
A comet is traveling through space with speed 3.73 ✕
104 m/s when it encounters an...
asked 36 minutes ago