Question

(Test perfect binary tree)

A perfect binary tree is a complete binary tree with all levels fully filled. Define a new class named BSTWithTestPerfect that extends BST with the following methods:

(Hint: The number of nodes in a perfect binary tree is 2^(height+1) - 1.)

/** Returns true if the tree is a perfect binary tree */ public boolean isPerfectBST()

Class Name: Exercise25_03

Answer 1

public class BST {

   /* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;

public Node(int item) {
key = item;
left = right = null;
}
}

// Root of BST
Node root;

// Constructor
BST() {
root = null;
}

// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
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.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);

/* return the (unchanged) node pointer */
return root;
}

// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}

// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}

}

public class BSTwithHEight extends BST {

   static int findADepth(Node node)
   {
   int d = 0;
   while (node != null)
   {
   d++;
   node = node.left;
   }
   return d;
   }
  
   /* This function tests if a binary tree is perfect
   or not. It basically checks for two things :
   1) All leaves are at same level
   2) All internal nodes have two children */
   static boolean isPerfectRec(Node root, int d, int level)
   {
   // An empty tree is perfect
   if (root == null)
   return true;
  
   // If leaf node, then its depth must be same as
   // depth of all other leaves.
   if (root.left == null && root.right == null)
   return (d == level+1);
  
   // If internal node and one child is empty
   if (root.left == null || root.right == null)
   return false;
  
   // Left and right subtrees must be perfect.
   return isPerfectRec(root.left, d, level+1) && isPerfectRec(root.right, d, level+1);
   }
  
   // Wrapper over isPerfectRec()
   static boolean isPerfect(Node root)
   {
   int d = findADepth(root);
   return isPerfectRec(root, d, 0);
   }
  
   public static void main(String[] args) {
       BSTwithHEight tree = new BSTwithHEight();
       tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
  
System.out.println("perfect : "+isPerfect(tree.root));
  

   }

}