IN JAVA- Please answer all of the questions! Try to get copy for sure! Modify th
ID: 3597344 • Letter: I
Question
IN JAVA- Please answer all of the questions! Try to get copy for sure!
Modify the author's BinarySearchTree code to implement the methods shown below Each method is 10 points. a) nodeCount Recursively traverses the tree and returns the count of nodes. b) isFull Returns true if the tree is ful1. A full tree has every node as either a leaf or a parent with two children c) compareStructure Compares the structure of current tree to another tree and returns true if they match. For example, these two trees have the same structure: 10 5 15 2 7 d) equals Compares the current tree to another tree and returns true if they are identical e) copy Creates and returns a new tree that is a copy of the original tree. f) mirror Creates and returns a new tree that is a mirror image of the original tree. For example, for the tree on the left, the tree on the right is returned: 100 100 50 150--> 150 50 40 40 45 45 g) isMirror Returns true if the tree is a mirror of the passed tree. h) rotateRight Performs a single rotation on the node having the passed value. If a RotateRight on 100 is performed: 100 50 50 150--> 40 100 40 45 150 45 g) rotateLeft As above but left rotation i) printLevels - performs a level-by-level printing of the tree. j) main - demonstrate in your main method that all of your new methods workExplanation / Answer
If you post more than 4 parts in 1 question, then as per chegg guidelines I have to answer only the first four parts.
// Assuming the structure of Node
class Node
{
// store the value of node
int data;
// pointer to left child
Node left;
// pointer to right child
Node right;
// constructor
Node()
{
data = 0;
left = null;
right = null;
}
// constructor
Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
(a)
// function to count the number of nodes in a tree
public int nodeCount(Node root)
{
// if the tree is empty
// then return 0
if(root == null)
return 0;
// recursively get the count of the
// number of nodes in left subtree
int left_subtree_count = nodeCount(root.left);
// recursively get the count of the
// number of nodes in right subtree
int right_subtree_count = nodeCount(root.right);
// return the total count of the current tree
// 1 is added for the current node
return 1 + left_subtree_count + right_subtree_count;
}
(b)
boolean isFull(Node root)
{
// if the tree is empty, then return true
if(root == null)
return true;
// if the current node is the leaf node
if(root.right == null && root.left == null)
return true;
// if the left child and right chld, both are not null
if(root.right != null && root.left != null)
{
// check if the right subtree is full
boolean is_right_full = isFull(root.right);
// check if the left subtree is full
boolean is_left_full = isFull(root.left);
return is_left_full && is_right_full;
}
// if the tree is not full
return false;
}
(c)
// check if the two trees are identical
boolean compareStructure(Node root1, Node root2)
{
// if both the trees are empty
if(root1 == null && root2 == null)
return true;
// if both trees are not empty
if(root1 != null && root2 != null)
{
// recursively check if the left and right subtree are also identical in structure
return compareStructure(root1.left, root2.left) && compareStructure(root1.right, root2.right);
}
// if the trees are not identical in structure
return false;
}
(d)
// check if the two trees are identical
boolean equals(Node root1, Node root2)
{
// if both the trees are empty
if(root1 == null && root2 == null)
return true;
// if both trees are not empty
if(root1 != null && root2 != null)
{
// recursively check if the left and right subtree are also identical
return root1.data == root2.data && equals(root1.left, root2.left) && equals(root1.right, root2.right);
}
// if the trees are not identical
return false;
}