Is Binary Tree Heap

You are given a binary tree, and the task is to determine whether it satisfies the properties of a max-heap.

A binary tree is considered a max-heap if it satisfies the following conditions:

1. Completeness: Every level of the tree, except possibly the last, is completely filled, and all nodes are as far left as possible.
2. Max-Heap Property: The value of each node is greater than or equal to the values of its children.

Examples:

Input: root[] = [97, 46, 37, 12, 3, 7, 31, 6, 9]
 
Output: true
Explanation: The tree is complete and satisfies the max-heap property.

Input: root[] = [97, 46, 37, 12, 3, 7, 31, N, 2, 4] 
 
Output: false
Explanation: The tree is not complete and does not follow the Max-Heap Property, hence it is not a max-heap.

Constraints:
1 ≤ number of nodes ≤ 10³
1 ≤ node->data ≤ 10³

Approach 01:

class Solution {
public:
    bool isHeap(Node* root) {
        int totalNodes = countNodes(root);
        return isComplete(root, 0, totalNodes) && checkHeap(root);
    }

private:
    int countNodes(Node* root) {
        if (!root)
            return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }

    bool isComplete(Node* root, int currentIndex, int totalNodes) {
        if (!root)
            return true;
        if (currentIndex >= totalNodes)
            return false;
        return isComplete(root->left, 2 * currentIndex + 1, totalNodes) &&
               isComplete(root->right, 2 * currentIndex + 2, totalNodes);
    }

    bool checkHeap(Node* root) {
        if (!root->left && !root->right)
            return true;
        if (!root->right)
            return root->data >= root->left->data && checkHeap(root->left);
        return root->data >= root->left->data &&
               root->data >= root->right->data &&
               checkHeap(root->left) &&
               checkHeap(root->right);
    }
};

class Solution:
    def isHeap(self, root):
        totalNodes = self.countNodes(root)
        return self.isComplete(root, 0, totalNodes) and self.checkHeap(root)

    def countNodes(self, root):
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def isComplete(self, root, currentIndex, totalNodes):
        if not root:
            return True
        if currentIndex >= totalNodes:
            return False
        return (self.isComplete(root.left, 2 * currentIndex + 1, totalNodes) and
                self.isComplete(root.right, 2 * currentIndex + 2, totalNodes))

    def checkHeap(self, root):
        if not root.left and not root.right:
            return True
        if not root.right:
            return root.data >= root.left.data and self.checkHeap(root.left)
        return (root.data >= root.left.data and
                root.data >= root.right.data and
                self.checkHeap(root.left) and
                self.checkHeap(root.right))

Time Complexity:

• Counting Nodes:

  The countNodes function visits each node once → \(O(n)\).

• Checking Completeness:

  The isComplete function also visits each node once → \(O(n)\).

• Checking Heap Property:

  The checkHeap function visits each node once → \(O(n)\).

• Total Time Complexity:

  \(O(n)\).

Space Complexity:

• Recursive Stack Space:

  Due to recursion, the maximum depth can be the height of the tree. In the worst case (completely skewed tree), height = \(n\), but for a complete binary tree (as in a heap), height = \(O(\log n)\).

• Total Space Complexity:

  \(O(\log n)\).