In this problem, you will write some Java code for simple operations on binary s

Question

In this problem, you will write some Java code for simple operations on binary search trees where keys are integers. Assume you already have the following code and assume that the method bodies, even though not shown, are correct and implement the operations as we defined them in class. public class BinarySearchTreeNode { public int key; public BinarySearchTreeNode left; public BinarySearchTreeNode right; } public class BinarySearchTree { private BinarySearchTreeNode root; public void insert(int key) { ... } public void delete(int key) { ... } public SomeType find(int key) { ... } } (a) Add a method public int keySum() to the BinarySearchTree class that returns the sum of all the keys in the tree. You will need an assistant/helper method. (b) Add method public void deleteMin() to the BinarySearchTree class that deletes the minimum element in the tree (or does nothing if the tree has no elements). c) Add method public void printTree() to the BinarySearchTree class that iterates over the nodes to print then in increasing order. So the tree... Produces the output "1 2 3 4 5". d) Add method public void printPostorder() to the BinarySearchTree class that prints out the nodes of the tree according to a "postorder" traversal. So the tree... Produces the output "1 3 2 5 4". e) You have a binary search tree. Consider a leave. B is the set of keys in the path p of including the leave and the root of the tree. A is the set of keys to the left of the path p. C is the set of keys to the right of the path p. Is the following statement true or false? Given any element a in A; b in B; c in C; a lessthanorequalto b lessthanorequalto c. Justify your answer.

Explanation / Answer

Considering all the code not shown is implemented and are correct, let's begin with the solution:
(a) The program can be simply done using recursion but as the question say to have a helper method. Here it is:

public int keySum() //this is the main method
{
return Sum(root); //calling sum root;
}

public int Sum(BinarySearchTreeNode root) //helper method
{
if(root==null) return 0;
if((root.left==null) && (root.right==null)) return 0; //both are null then 0
return root.key + Sum(root.left) + Sum(root.right); //sum the left and the right node
}

(b) Logically speaking, the minimum is just the leftmost elements in a binary search tree. Once, we reach there we just have to make the it's parent node pointing to it null. Here is how you do it:
public void deleteMin()
{
BinarySearchTreeNode prev; //one previous node (parent node)
int minv = root.key;
while (root.left != null)
{
minv = root.left.key;
prev = root;
root = root.left;
}
prev.left = null; (parent has no left child now i.e. no min value
}

(c) This is just an inorder traversal, so we need to have an assitant method. Here goes:

public void printTree(){
printIn(root); //calling the function
}

void printIn(Node node)
{
if (node == null)
return;
printIn(node.left); //first left node is printed
System.out.print(node.key + " "); //then root
printIn(node.right); // then right node
}

(d) We just have to switch order in the above program to print the post order.

public void printPostorder(){
printPost(root); //calling the function
}

void printPost(Node node)
{
if (node == null)
return;
printPost(node.left); //first left node is printed
printPost(node.right); //then right
System.out.print(node.key + " "); // then root node
}

(e) The statement is false. Let's consider an example:
We have the following BST:
8
4
3 6

I can't draw it here, you probably get it from the figure that 8 is the root node then it has only one left child i.e. 4 and 4 has further two child, left is 3 and right is 6.
Let's say we search for the leaf node i.e. 3. Now, according to the definition provided of the sets A, B and C. We start from 8, not found move to 4, found. So, 8, 4 and 3 will be in set B. Now, set A is empty and set C has only 6.
a <= b <= c is true for all the elements but b has 8 also which makes this statement false. Hence, it is justified that the statement is not true.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.