# Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children.

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

In simple terms should every node in the subtree of a root be smaller than the root?

• hm... I would say it does not apply recursively. Do you see any benefits to using the definition which is recursive? Jun 9, 2020 at 0:24
• @KevinWang I didn't think it in terms of benefits but rather the clarity of definition. Jun 9, 2020 at 7:00

I would think that most people would just say that the heap property applies only to a vertex and its immediate children, because it's a sufficient definition to maintain the "recursive" heap property everywhere. It's a cleaner way to think about it (you only need to check O(1) objects per vertex to verify that a tree is a heap, as opposed to O(n) per vertex).

I don't know if there is exactly a consensus on this, and perhaps some other people think differently.