Python

class LN: def __init__(self,value,next=None): self.value = value self.next = next

def list_to_ll(l): if l == []: return None front = rear = LN(l[0]) for v in l[1:]: rear.next = LN(v) rear = rear.next return front

def str_ll(ll): answer = '' while ll != None: answer += str(ll.value)+'->' ll = ll.next return answer + 'None'

# Tree Node class and helper functions (to set up problem)

class TN: def __init__(self,value,left=None,right=None): self.value = value self.left = left self.right = right

def list_to_tree(alist): if alist == None: return None else: return TN(alist[0],list_to_tree(alist[1]),list_to_tree(alist[2])) def str_tree(atree,indent_char ='.',indent_delta=2): def str_tree_1(indent,atree): if atree == None: return '' else: answer = '' answer += str_tree_1(indent+indent_delta,atree.right) answer += indent*indent_char+str(atree.value)+' ' answer += str_tree_1(indent+indent_delta,atree.left) return answer return str_tree_1(0,atree)

def is_min_heap(t): pass

print(' Testing is_min_heap') t = None print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([1,[2,None,None],[3,None,None]]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([2,[1,None,None],[3,None,None]]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([3,[2,None,None],[1,None,None]]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([1,None,[3,None,None]]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([1,[2,None,None],None]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([3,None,[1,None,None]]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree([2,[1,None,None],None]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree( [5, [8, [16, [32,None,None], [46, [70,None,None], [82,None,None] ] ], None], [12, [24, None, [30, [40,None,None], [70,None,None] ] ], None ] ]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t)) t = list_to_tree( [5, [8, [16, [32,None,None], [32, [70,None,None], [82,None,None] ] ], None], [12, [30, None, [30, [40,None,None], [70,None,None] ] ], None ] ]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t))

t = list_to_tree( [5, [8, [16, [32,None,None], [46, [70,None,None], [82,None,None] ] ], None], [12, [30, None, [30, [40,None,None], [70,None,None] ] ], None ] ]) print(' Tree is ',str_tree(t),end='') print('is_min_heap =',is_min_heap(t))

its children (if a left/right child is None, you don't have to check it). Write the recursive function is_min heap which checks this order property for every node in the tree and returns True if the binary tree is a min-heap and False if it is not. Think symmetry