Is Binary Tree Heap

Time: O(n)

Space: O(n)

Intuition

Check two properties: complete binary tree (all levels full except last, last filled left to right) and max-heap property (parent >= children).

Algorithm

1BFS level order. Once a non-full node is seen, all subsequent nodes must be leaves (completeness check).
2For each node: check node.val >= children values (max-heap property).

Common Pitfalls

•Both conditions must hold simultaneously. Completeness check: after first missing child, no more children should appear.

Is Binary Tree Heap.java

Java

// Approach: Check completeness with BFS (once a null is seen, no more nodes should follow).
// Verify heap property by DFS checking parent >= children.
// Time: O(n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    boolean isHeap(Node tree) {
        Queue<Node> q = new LinkedList<>();
        q.add(tree);
        while (!q.isEmpty()) {
            boolean siblingChild = true;
            int size = q.size();
            for (int i = 1; i <= size; i++) {
                Node curr = q.remove();
                // tree completeness check
                if (curr.left == null && curr.right != null)
                    return false;
                if ((curr.left != null || curr.right != null) && !siblingChild)
                    return false;

                // max-heap check
                if ((curr.left != null && curr.data < curr.left.data) ||
                        (curr.right != null && curr.data < curr.right.data))
                    return false;

                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);

                // tree-completeness maintenance
                if (curr.left == null || curr.right == null)
                    siblingChild = false;
            }
        }

        return true;
    }
}

Was this solution helpful?