Complete the code for the four problems that follow. Leave everything as a publi
ID: 3886938 • Letter: C
Question
Complete the code for the four problems that follow. Leave everything as a public boolean. Possibly relevant code is included here:
public int size () {
return size (root, 0);
}
private static int size (Node x, int sz) {
if (x != null) {
sz = sz + 1;
sz = size (x.left, sz);
sz = size (x.right, sz);
}
return sz;
}
// the height of the tree
public int height() {
return height(this.root);
}
private int height(Node current) {
if (current == null) {
return -1;
}
else {
return 1+ Math.max(height(current.left), height(current.right));
}
}
THINGS NEEDING SOLVING STARTS HERE:
#1
// tree is perfect if for every node, size of left == size of right
// hint: in the helper, return -1 if the tree is not perfect, otherwise return the size
public boolean isPerfectlyBalancedS() {
// TODO: complete code
return false;
}
#2
// tree is perfect if for every node, height of left == height of right
// hint: in the helper, return -2 if the tree is not perfect, otherwise return the height
public boolean isPerfectlyBalancedH() {
// TODO: complete code
return false;
}
#3
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced() {
// TODO: complete code
return false;
}
#4
// tree is semi-perfect if every node is semi-perfect
// A node with 0 children is semi-perfect.
// A node with 1 child is NOT semi-perfect.
// A node with 2 children is semi-perfect if (size-of-larger-child <= size-of-smaller-child * 3)
// hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size
public boolean isSemiBalanced() {
// TODO: complete code
return false;
}
Explanation / Answer
class Node
{
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class BinaryTree
{
Node root;
boolean isBalancedS(Node node)
{
int lh;
int rh;
/* If tree is empty then return true */
if (node == null)
return true;
/* Get the height of left and right sub trees */
lh = size(node.left);
rh = size(node.right);
if (Math.abs(lh - rh) <= 1
&& isBalancedS(node.left)
&& isBalancedS(node.right))
return true;
/* If we reach here then tree is not height-balanced */
return false;
}
boolean isBalancedH(Node node)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (node == null)
return true;
/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);
if (Math.abs(lh - rh) <= 1
&& isBalancedH(node.left)
&& isBalancedH(node.right))
return true;
/* If we reach here then tree is not height-balanced */
return false;
}
class OddCounter {
int count = 0;
}
boolean isOddBalanced(Node node)
{
OddCounter c = new OddCounter();
isOddBalancedHelper(root, c, '0');
return (c.count == 0);
}
private void isOddBalancedHelper (Node x, OddCounter c, char comingFrom) {
if (x == null) return;
isOddBalancedHelper(x.left, c, 'l');
isOddBalancedHelper(x.right, c, 'r');
if(x.value % 2 != 0 && comingFrom == 'l') { // if current node is odd and a left child
c.count++;
} else if(x.value % 2 != 0 && comingFrom == 'r') { // if current node is odd and a right child
c.count--;
}
}
int size(Node node)
{
if(node == null)
return 0;
return 1 + size(node.left) + size(node.right);
}
int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.left.left.left = new Node(8);
if(tree.isBalancedH(tree.root))
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.