Determine if a binary tree rooted at a node is a max-heap

Question

I'm trying to determine if a binary tree rooted at a node is a max-heap, and to do so I followed the rules of the heap property for a max-heap which states:

Max-heap:

All nodes are either greater than or equal to each of its children

My Idea of the implementation:

If at the node given as the parameter of is_max_heap has no right or left node than return True
Otherwise, if the value of the node is greater than the value of the left and right node, then call the function again on both the right and left nodes.
Return False otherwise.

My code:

class BTNode:
    '''A generic binary tree node.'''

    def __init__(self, v):
        '''(BTNode, int) -> NoneType

        Initialize a new BTNode with value v.

        '''
        self.value = v
        self.left = None
        self.right = None


def is_max_heap(node):
    '''(BTNode) -> bool

    Return True iff the binary tree rooted at node is a max-heap
    Precondition: the tree is complete.

    '''
    if node.left and node.right is None:
        return True
    else:
        if node.value > node.left.value and node.value > node.right.value:
            return is_max_heap(node.left) and is_max_heap(node.right)
        else:
            return False


if __name__ == '__main__':
    l1 = BTNode(7)
    l2 = BTNode(6)
    l3 = BTNode(8)
    l1.left = l2
    l1.right = l3
    print(is_max_heap(l1))

So, under if __name__ == '__main__': I created three nodes, with values, 7, 6, and 8. The first node has a left and right node. So the tree would look like this:

   7
 /   \
6     8

This does not satisfy the max-heap property so it should return False. However running my code returns True and I can't figure out where I might of went wrong. If anyone can help me that would be really appreciated.

`if node.left and node.right is None` should read `if not (node.left or node.right)`. — Hyperboreus, Apr 22 '14 at 20:12
Really `if node.left is None and node.right is None:`; you should test for `None` with identity rather than equality. — jonrsharpe, Apr 22 '14 at 20:20
@jonrsharpe very good point. He's not even testing for equality though (`value == None`), but doing an implicit cast to boolean using `not value`, which would produce surprising results for nodes with a value of `0` or empty string. — Lukas Graf, Apr 22 '14 at 20:24
@LukasGraf `left` and `right` are either `None` or an instance of `BTNode` as I read the code. How can an instance of `BTNode` be an empty string or `0`? — Hyperboreus, Apr 22 '14 at 20:28
@Hyperboreus indeed, I just realized that, never mind my comment. — Lukas Graf, Apr 22 '14 at 20:29
@jonrsharpe Where do I test for equality? `left` and `right` are either `None` or an instance of `BTNode` as I read the code, and as `BTNode` doesn't implement `__bool__` any instance of `BTNode` will be truey. — Hyperboreus, Apr 22 '14 at 20:33
@Hyperboreus not really equality so much truthiness, yes, but "Comparisons to singletons like `None` should always be done with `is` or `is not`" per PEP-008. — jonrsharpe, Apr 22 '14 at 20:38

Has QUIT--Anony-Mousse · Accepted Answer · 2014-04-22T21:00:42.533

0

You have not thought of the case when there is only one child. Make sure your program works right on these two trees, too - one is a min heap, the other is a max heap:

  2     1
 /     /
1     2

Also learn to set brackets correctly; you have made the classic mistake True and 42 == 42; which is True.

Consider handling the two maybe-nonexistant childs the same way.

if left is not None:
  if not <check max heap property for left subtree>: return False
if right is not None:
  if not <check max heap property for right subtree>: return False
return True

The missing function should compare to the current node and recurse into the subtree if necessary.

edited Apr 22 '14 at 21:00

answered Apr 22 '14 at 20:46

Has QUIT--Anony-Mousse

76,138
12
138
194

In a Max-Heap you will never have the case that there is a right child but no left child. This is because a Max-Heap is a complete Binary-Tree (all internal nodes have 2 children) and in the last row it's filled up "from left to right". So if any node has only one child, it must be a left child. – m4110c Aug 16 '20 at 12:09

Determine if a binary tree rooted at a node is a max-heap

1 Answers1