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
– Martin Konecny, Commented May 22, 2015 at 1:21
Is that recursive? There is a base case, OK, but there is no call to itself in no point? — rafaelc
– rafaelc, Commented May 22, 2015 at 1:49

Martin Konecny · Accepted Answer · 2015-05-22 01:52:43Z

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, 2015 at 1:52

Martin Konecny

60k20 gold badges144 silver badges159 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

dustinyourface Over a year ago

In the second and third if statements, aren't t.left and t.right trees?

Martin Konecny Over a year ago

yes, if t.left just makes sure that it's not None. Otherwise t.left.value would fail.

dustinyourface Over a year ago

ooh ok. So that code is the same as if t.left != None and t.value > t.left.value:?

Martin Konecny Over a year ago

yes exactly. But you should write that as t.left is not None

dustinyourface Over a year ago

Why is it better to write it that way?

Collectives™ on Stack Overflow

Recursive function for min-heap binary tree

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related