I need help with designing the following methods for working on a binary tree. I

Question

I need help with designing the following methods for working on a binary tree. I only need to see what the methods look like. The methods are in JAVA.

boolean update (int oldValue, int newValue)

-Searches for oldValue in the tree. If found, the data for that node is changed to newValue and the tree is modified such that the node with the new value is placed in the appropriate place in the tree and returns true

-If the oldValue is not found in the tree, the function returns false and the tree stays as is

int findMin()

-If the tree is empty, return -1

-Otherwise, return the smallest value node in the tree

int findMax()

-If the tree is empty, return -1

-Otherwise, return the largest value node in the tree

double calculateAverage()

-If the tree is empty, return 0.0

-Otherwise, return the average value of the tree by adding all node values and dividing by the number of nodes in the tree

int getNumberOfNodes()

-Returns the number of nodes in the tree

boolean isBalanced()

-If the tree is empty, return false

-Otherwise, return true if the tree is balanced

-A balanced is tree is defined as follows:

If both of its subtrees are balanced

The height of its left subtree differs from the height of its right subtree by at most 1

Explanation / Answer

Binary tree is a node which has 1 data node and 2 pointers which pointed to its left and right child.

let say data is data node, left is left child of node and right is right child of node. And Tree has one special pointer head, which points to starting of tree. Let's make a class of binary tree.
class node{

node right, left;

int data;

implement their getter and setter functions.

}

make another class for Binary Tree

class BinaryTree{

private Node head;

BinaryTree(){

head = null;

}

private boolean updateUtil (Node r, int oldVal, int newVal)
{

if (r.getData() == oldVal){ // if oldValue find, replace it with newvalue
r.setData(newVal);
return true
}
if (r.getLeft() != null)
return updateUtil(r.getLeft(), oldVal, newVal); // search in left subtree
if (r.getRight() != null)
return updateUtil(r.getRight(), oldVal, newVal); // search in right subtree
return false;
}

boolean update(int oldValue, int newValue){
if (head == null) return false;
return updateUtil(head, oldValue, newValue)
}

private int findMinTree(Node r, int min)
{

if (r.getData() < min) // update first data if minimun value find
min = r.getData();

if (r.getLeft() != null)
return findMinTree(r.getLeft(), min);

if (r.getRight() != null)
return findMinTree(r.getRight(), min);

return min;
}

int findMin()
{
if (head == null) {
return -1;}
int min = head.getData(); // make first data minimum value first

return findMinTree(head, min)   
}
private int findMaxTree(Node r, int max)
{
if (r.getData() > max) // update if current data is maximum that old max
max = r.getData();
if (r.getLeft() != null)
return findMaxTree(r.getLeft(), max);
if (r.getRight() != null)
return findMaxTree(r.getRight(), max);

return max;
}
int findMax()
{
if (head == null) {
return -1;
}
int max = head.getData(); // make first item max element
return findMaxTree(head, max);
}
  
private double TotalSum(Node r)
{
double total = r.getData(); // current node value
if (r.getLeft() != null)
total += TotalSum(r.getLeft()); // add left subtree value
if (r.getRight() != null)
total += TotalSum(r.getRight()); // add right subtree value
return total;
}

private int getNumberofNodesUtil(Node r){
int count = 1; // count current node
if (r.getLeft() != null)
count += getNumberofNodesUtil(r.getLeft()); // if left path is not null, cover it
if (r.getRight() != null)
count += getNumberofNodesUtil(r.getRight()); // if right path is not null, cover it
return count;
}

int getNumberOfNodes(){ // function that count number of nodes
if (head == null) return 0;
return getNumberofNodesUtil(head);
}

double calculateAverage()
{
if (head == null)
return 0.0;
double total = TotalSum(head); // calculate total sum of tree
int count = getNumberOfNodes(); // get total number of nodes
return total/count; // return average
}

private int isBalancedUtil(Node r){
if (r==null) return 0; // node is null return height zero
int l = isBalancedUtil(r.getLeft()); // calculate left subtree height
int r = isBalancedUtil(r.getRight()); // calculate right subtree height
if (l>r) return l+1; // if left subtree height is max return its height and add one for this node
else return r+1; // same for right subtree

}

boolean isBalanced()
{
if (head== null) return false;
int l = isBalancedUtil(head.getLeft());
int r = isBalancedUtil(head.getRight());
int diff = l - r; // caculate difference between right and left subtree
if (diff == 0 || diff == 1 || diff == -1) return true; // if balanced by 1 return true
else false;
}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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