HeapProblem 13 of 18
Check if a Binary Tree is Heap
Problem Statement
Given a binary tree, check if it follows the heap property. A binary tree is a heap if:
- It is a complete binary tree (all levels are fully filled except possibly the last level, which is filled from left to right)
- Every node's value is greater than or equal to its children's values (for max-heap)
Example:
-
Input:
10 / \ 9 8 / \ / 7 6 5 -
Output:
true(It's a valid max-heap) -
Input:
10 / \ 5 9 / \ 7 6 -
Output:
false(5 < 7 and 5 < 6, violates max-heap property)
Approach 1: Level Order Traversal
Intuition
Use level order traversal to check both completeness and heap property. A tree is complete if no null node appears before a non-null node in level order.
Algorithm
- Do level order traversal
- Once a null child is seen, all subsequent children must be null (completeness)
- Each node's value must be >= its children's values (heap property)
java
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
public boolean isHeap(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean nullSeen = false;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// Check left child
if (node.left != null) {
if (nullSeen) return false;
if (node.left.val > node.val) return false;
queue.offer(node.left);
} else {
nullSeen = true;
}
// Check right child
if (node.right != null) {
if (nullSeen) return false;
if (node.right.val > node.val) return false;
queue.offer(node.right);
} else {
nullSeen = true;
}
}
return true;
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - Queue can hold up to n/2 nodes at last level
Approach 2: Recursive with Node Counting
Intuition
First count total nodes. Then check if tree is complete by verifying index constraints, and simultaneously check heap property.
Algorithm
- Count total nodes in tree
- For each node at index i (0-indexed):
- Left child should be at 2i+1 (must be < total nodes)
- Right child should be at 2i+2 (must be < total nodes)
- Check heap property at each node
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
private int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
private boolean isCompleteAndHeap(TreeNode root, int index, int totalNodes) {
if (root == null) return true;
// If index >= total nodes, not complete
if (index >= totalNodes) return false;
// Check heap property
if (root.left != null && root.left.val > root.val) return false;
if (root.right != null && root.right.val > root.val) return false;
// Recursively check children
return isCompleteAndHeap(root.left, 2 * index + 1, totalNodes) &&
isCompleteAndHeap(root.right, 2 * index + 2, totalNodes);
}
public boolean isHeap(TreeNode root) {
int totalNodes = countNodes(root);
return isCompleteAndHeap(root, 0, totalNodes);
}
}Complexity Analysis
- Time Complexity: O(n) - Count nodes O(n), check O(n)
- Space Complexity: O(h) - Recursion stack, h is tree height
Approach 3: Single Pass with Pair Return
Intuition
Combine completeness and heap check in a single traversal by returning multiple values from recursive calls.
Algorithm
- Return a tuple: (isHeap, nodeCount, isComplete)
- A subtree is complete if both children are complete and have proper counts
- Check heap property at each node
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
// Returns [isHeap, nodeCount]
private int[] checkHeap(TreeNode root) {
if (root == null) {
return new int[]{1, 0}; // 1 = true, 0 = false
}
int[] leftResult = checkHeap(root.left);
int[] rightResult = checkHeap(root.right);
// Both subtrees must be heaps
if (leftResult[0] == 0 || rightResult[0] == 0) {
return new int[]{0, 0};
}
// Check heap property
if (root.left != null && root.left.val > root.val) {
return new int[]{0, 0};
}
if (root.right != null && root.right.val > root.val) {
return new int[]{0, 0};
}
int leftCount = leftResult[1];
int rightCount = rightResult[1];
int totalCount = 1 + leftCount + rightCount;
// Check completeness
boolean isComplete = (leftCount >= rightCount) &&
(leftCount <= 2 * rightCount + 1);
return new int[]{isComplete ? 1 : 0, totalCount};
}
public boolean isHeap(TreeNode root) {
return checkHeap(root)[0] == 1;
}
}Complexity Analysis
- Time Complexity: O(n) - Single traversal
- Space Complexity: O(h) - Recursion stack
Key Takeaways
- A binary tree heap must be complete AND satisfy heap property
- Level order traversal elegantly checks completeness: once null seen, all must be null
- Index-based check: for node at index i, children at 2i+1 and 2i+2 must be < total nodes
- Heap property: Every parent must be >= (max-heap) or <= (min-heap) its children
- For min-heap, just reverse the comparison
- This problem combines two concepts: complete binary tree + heap property
- Both BFS (level order) and DFS (recursive) solutions achieve O(n) time