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

Question

This question already has answers here:

How to test multiple variables for equality against a single value? (31 answers)

Closed 9 years ago.

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:

1. If at the node given as the parameter of is_max_heap has no right or left node than return True
2. 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.
3. 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.

Answer 1

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.