Question

Assessment O Submissions.. l import java.util.List; 2 import java.util.Arraylist; 4 public class ArrayHeapChecker 7Checks if the given array is a representation of a binary tree * @param entries 10 array of entries to be test * ereturn true if the input array encodes a binary tree, false otherwise 12 13 14 public static <K extends Comparable K, vs boolean isBinaryTree(List Entry<k,v entries) ( 15 16 17 // TODO: implement this return true 18 19 2e 21 * Checks if the given array is a complete binary tr + eparam entries 23 24 25 26 array of entries to be tested ereturn true if the input array encodes a complete binary tree, false otherwise os entries) 27 public static <k extends Comparablecki, vi boolean iscompletesinarytree(List Entryx, v if (!isBinaryTree (entries)) ( 28 29 return false; 31 /I TODO: implement this All changes saved Run Submit File: /home/ArrayHeapChecker java 1:1 Console Feedback Terminal

Answer 1

import java.util.List;

public class ArrayHeapChecker {

    public static <K extends Comparable<K>, V> boolean isBinaryTree(List<Entry<K, V>> entries) {
        boolean isBinaryTree = true;

        // check the node except the root node.. if there is just root node
        // it is always a binary tree
        if(entries.size() > 1) {
            for(int i = 1; i < entries.size(); i++) {
                if(entries.get(i) != null) {
                    int parentIndex = Math.floorDiv((i-1), 2);
                    if(entries.get(parentIndex) == null) {
                        return false;
                    }
                }
            }
        }

        return isBinaryTree;
    }

    public static <K extends Comparable<K>, V> boolean isCompleteBinaryTree(List<Entry<K, V>> entries) {
        if(!isBinaryTree(entries)) {
            return false;
        }

        if(entries.size() == 0)
            return true;

        int treeHeight = arrayBinaryTreeHeight(0, entries);

        if(treeHeight == 0)
            return true;

        int lowestLevelStart = (int) Math.pow(2, treeHeight) - 1;
        boolean allNull = true;
        boolean someNull = false;

        for(int i = 0; i < lowestLevelStart; i++){
            if(entries.get(i) == null)
                someNull = true;

            if(entries.get(i) != null)
                allNull = false;
        }

        if(!allNull && someNull)
            return false;


        someNull = false;
        for(int i = lowestLevelStart; i < entries.size(); i++){
            if(entries.get(i) == null)
                someNull = true;

            if(entries.get(i) != null && someNull)
                return false;
        }

        return true;
    }

    public static <K extends Comparable<K>, V> int arrayBinaryTreeHeight(int index, List<Entry<K, V>> entries) {
        if(index >= entries.size())
            return 0;
        if(entries.get(index) == null)
            return 0;

        Entry<K, V> left;
        Entry<K, V> right;

        if(index*2 + 1 >= entries.size() || index*2 + 2 >= entries.size()){
            left = right = null;
        } else {
            left = entries.get(index*2 + 1);
            right = entries.get(index*2 + 2);
        }

        if(left == null && right == null){
            return 0;
        }

        int h = 0;
        if(left != null)
            h = Math.max(h, arrayBinaryTreeHeight((index*2 + 1), entries));

        if(right != null)
            h = Math.max(h, arrayBinaryTreeHeight((index*2 + 2), entries));

        return 1 + h;
    }



    public static <K extends Comparable<K>, V> boolean isMinHeap(List<Entry<K, V>> entries) {
        if(!isCompleteBinaryTree(entries)) {
            return false;
        }
        return isMinHeap(entries, 0);
    }

    public static <K extends Comparable<K>, V> boolean isMinHeap(List<Entry<K, V>> entries, int index) {
        if(index >= entries.size())
            return true;

        Entry<K, V> parentVal = entries.get(index);
        int leftIndex = index*2 + 1;
        int rightIndex = index*2 + 2;

        if(rightIndex < entries.size()){
            Entry<K, V> leftVal = entries.get(leftIndex);
            Entry<K, V> rightVal = entries.get(rightIndex);

            if(leftVal != null && rightVal != null){
                if ((leftVal.getKey().compareTo(parentVal.getKey()) < 0) || (rightVal.getKey().compareTo(parentVal.getKey()) < 0)) {
                    return false;
                } else {
                    return isMinHeap(entries, leftIndex) && isMinHeap(entries, rightIndex);
                }
            }

            if(leftVal != null){
                return true && isMinHeap(entries, leftIndex);
            } else {
                return true;
            }
        } else {
            return true;
        }
    }

    public static class Entry<K extends Comparable<K>, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

    public static void main(String args[]) {

    }
}

============

Hi. please find the answer above.. i have given comments so that it is very easy for you to understand the flow. In case of any doubts, please ask in comments. If the answer helps you, please upvote. Thanks!