Check whether a binary tree is a heap

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}