Must be done in java: LIBRARIES available to USE: java.util.linkedlist, java.uti
ID: 3919296 • Letter: M
Question
Must be done in java: LIBRARIES available to USE: java.util.linkedlist, java.util.stack, java.util.queue
Objective: The goal of this assignment is to practice the use of binary search trees.
Assignment: Write several recursive methods related to trees:
-a method that, given a binary search tree, returns its smallest element;
-a method that, given a binary search tree, returns its largest element;
-a method that, given a binary search tree, returns the total number of elements in the tree;
-a method that, given a binary search tree, returns its height;
-a method that, given an element and a binary search tree, checks whether this element belongs to this tree;
-a method that, given an element and a binary search tree, adds this element to the tree.
Main idea. For example, to find a given element in a given tree, we do the following. First, we check whether the tree is empty. If the tree is empty, then the given element is not there, otherwise we compare the given element with the root of the tree:
-if the element is equal to the root, we return "true";
-if the element is smaller than the root, we search in the left subtree;
-if the element is larger than the root, we search in the right subtree.
Explanation / Answer
/* Given a non-empty binary search tree,
return the minimum data value found in that
tree. Note that the entire tree does not need
to be searched. */
public int minvalue(Node node) {
if(node.left == null) {
return node.data;
}
minValue(node.left);
}
/* Given a non-empty binary search tree,
return the maximum data value found in that
tree. Note that the entire tree does not need
to be searched. */
public int maxvalue(Node node) {
if(node.right == null) {
return node.data;
}
maxValue(node.right);
}
public int countOfNodes(Node node) {
if(node == null)
return 0;
int nLeftSubtree = countOfNodes(node.left);
int nRightSubtree = countOfNodes(node.right);
return nLeftSubtree + nRightSubtree + 1;
}
public int height(Node node)
{
if (node == null)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = height(node.left);
int rDepth = height(node.right);
/* use the larger one */
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
public boolean search(Node node, int key)
{
// Base Cases: root is null or key is present at root
if (node == null || node.data==key)
return true;
// val is greater than root's key
if (node.data > key)
return search(node.left, key);
// val is less than root's key
return search(node.right, key);
}
//This method mainly calls insertRec()
public void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
public 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.data)
root.left = insertRec(root.left, key);
else if (key > root.data)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.