Check whether a binary tree is a heap
Problem
Return true if the binary tree is a max-heap: it is complete (every level full except possibly the last, which is filled from the left), and every node is at least as large as its children.
Example 1
Input: [97, 46, 37, 12, 3, 7, 31, 6, 9] Output: true
Also asked as: Check if a Binary Tree is Heap
Test cases
Case 1
Input: [97,46,37,12,3,7,31,6,9] Expected: true
Case 2
Input: [1,2,3] Expected: false
Case 3
Input: [10,9,null,8] Expected: false
Case 4
Input: [5] Expected: true
View solutionHide solution1 approach
1. Complete-tree check + heap-order check
Time O(n)Space O(h)
Count nodes; a node at index i is valid only if i < count (completeness). Separately verify every node ≥ its children (max-heap).
function isHeap(root) { const count = (n) => (n ? 1 + count(n.left) + count(n.right) : 0); const total = count(root); const complete = (n, i) => { if (!n) return true; if (i >= total) return false; return complete(n.left, 2 * i + 1) && complete(n.right, 2 * i + 2); }; const ordered = (n) => { if (!n) return true; if (n.left && n.left.val > n.val) return false; if (n.right && n.right.val > n.val) return false; return ordered(n.left) && ordered(n.right); }; return complete(root, 0) && ordered(root);}