Question

Program in JAVA: A Perfect binary tree is a complete binary tree with all levels fully filled. Add a method in the BST class to return true if the tree is a perfect binary tree.(Hint: The number of nodes in the nonempty perfect binary tree is 2 raised to the power of height - 1) (/** returns true if the tree is a perfect binary tree, boolean isPerfectBST() **/)

Answer 1

package aug02;
public class BinaryTree {

        public int value;
        private BinaryTree leftChild;
        private BinaryTree rightChild;

        /**
         * Constructor for BinaryTree
         */
        public BinaryTree(int value, BinaryTree leftChild, BinaryTree rightChild) {
                this.value = value;
                this.leftChild = leftChild;
                this.rightChild = rightChild;
        }

        public BinaryTree(int value) {
                this(value, null, null);
        }
        
        public int getValue() {
                return value;
        }

        public BinaryTree getLeftChild() {
                return leftChild;
        }

        public BinaryTree getRightChild() {
                return rightChild;
        }

        public void setLeftChild(BinaryTree leftChild) {
                this.leftChild = leftChild;
        }

        public void setRightChild(BinaryTree rightChild) {
                this.rightChild = rightChild;
        }

        public static void printInorder(BinaryTree start) {
                if(start.getLeftChild() != null) {
                        printInorder(start.getLeftChild());
                }
                System.out.print(" " + start.getValue());
                if(start.getRightChild() != null) {
                        printInorder(start.getRightChild());
                }
        }
        
        
        public static BinaryTree createFullBST(int depth) {
                BinaryTree root = new BinaryTree((int) Math.pow(2, depth));
                
                addFullBSTNodes(root, 0, depth);
                
                return root;
        }
        
        private static void addFullBSTNodes(BinaryTree start, int currentDepth, int maxDepth) {
                // base case
                if(currentDepth == maxDepth) {
                        return;
                }
                int rootValue = start.getValue();
                int diff = (int) Math.pow(2, maxDepth - currentDepth - 1);
                BinaryTree left = new BinaryTree(rootValue - diff);
                start.setLeftChild(left);
                BinaryTree right = new BinaryTree(rootValue + diff); 
                start.setRightChild(right);
                
                addFullBSTNodes(left, currentDepth + 1, maxDepth);
                addFullBSTNodes(right, currentDepth + 1, maxDepth);
        }

        public int countNodesInRange(int min, int max) {
                int count = 0;
                if(value >= min && value <= max) {
                        count++;
                }
                if(leftChild != null) {
                        count += leftChild.countNodesInRange(min, max);
                }
                if(rightChild != null) {
                        count += rightChild.countNodesInRange(min, max);
                }
                return count;
        }

        
        public int maxValue() {
                int max = value;
                if(leftChild != null) {
                        int val = leftChild.maxValue();
                        if(val > max) {
                                max = val;
                        }
                }
                if(rightChild != null) {
                        int val = rightChild.maxValue();
                        if(val > max) {
                                max = val;
                        }
                }
                return max;
        }
        
        public int nodesWithNoSons() {
                int count = 0;
                if(leftChild == null && rightChild == null) {
                        return 1;
                }
                if(leftChild != null) {
                        count += leftChild.nodesWithNoSons();
                } 
                if(rightChild != null) {
                        count += rightChild.nodesWithNoSons();
                }
                return count;
        }

        public int height() {
                int left = 0, right = 0;
                if(leftChild != null) {
                        left = leftChild.height();
                }
                if(rightChild != null) {
                        right = rightChild.height();
                }
                return 1 + Math.max(left, right);
        }
        
        public int numNodes() {
                int left = 0, right = 0;
                if(leftChild != null) {
                        left = leftChild.numNodes();
                }
                if(rightChild != null) {
                        right = rightChild.numNodes();
                }
                return 1 + left + right;
        }
        
        public boolean isPerfectBST() {
                int n = numNodes();
                int h = height();
                return ((n + 1) == Math.pow(2, h));
        }
        
        public static void main(String args[]) {
                BinaryTree tree = createFullBST(6);
                printInorder(tree);
                System.out.println();
                
                System.out.println("Max value: " + tree.maxValue());
                System.out.println("nodes between 59 and 112: " + tree.countNodesInRange(59, 112));
                System.out.println("nodes with no sons: " + tree.nodesWithNoSons());
                System.out.println("Is perfect: " + tree.isPerfectBST());
        }
        

}

Please upvote, as i have given the exact answer as asked in question. Still in case of any issues in code, let me know in comments. Thanks!