Recursive function for min-heap binary tree

Question

I have been stuck on solving this task for quite a while. I need to write a recursive function to check whether that every node is smaller than any of its children. Returns true if the binary tree is a min-heap and false otherwise.

What i have so far:

def min_heap(t):
    if t == None:
        return True
    else:
        return t.left.value > t.value and t.right.value > t.value

"I have been stuck on solving this task for quite a while" - show us what you have — Martin Konecny, May 22 '15 at 01:21
Is that recursive? There is a base case, OK, but there is no call to itself in no point? — rafaelc, May 22 '15 at 01:49

score 1 · Answer 1 · answered May 22 '15 at 01:52

1

If it's recursive, that means it should be calling itself. Assuming your min-heap by definition is

every node is smaller than any of its children

def min_heap(t):
    if t == None:
        return True
    if t.left and t.value > t.left.value:
        return False
    if t.right and t.value > t.right.value:
        return False
    return min_heap(t.left) and min_heap(t.right)

answered May 22 '15 at 01:52

Martin Konecny

57,827
19
139
159

In the second and third if statements, aren't t.left and t.right trees? – dustinyourface May 22 '15 at 02:20
yes, `if t.left` just makes sure that it's not `None`. Otherwise `t.left.value` would fail. – Martin Konecny May 22 '15 at 02:21
ooh ok. So that code is the same as `if t.left != None and t.value > t.left.value:`? – dustinyourface May 22 '15 at 02:26
yes exactly. But you should write that as `t.left is not None` – Martin Konecny May 22 '15 at 02:27
Why is it better to write it that way? – dustinyourface May 22 '15 at 04:25

Recursive function for min-heap binary tree

1 Answers1