Trees: Difficult Solutions

Code Writing

Write a function that mutates a tree by adding the level number to each label on the level, where the root node is on level 1.
def levels(tree):
>>> t = Tree(1, [Tree(4, [Tree(5)]), Tree(6)])
>>> levels(t)
Tree(2, [Tree(6, [Tree(8)]), Tree(8)])
>>> t
Tree(2, [Tree(6, [Tree(8)]), Tree(8)])
def level_helper(tree, level_num):
tree.label += level_num
for b in tree.branches
level_helper(b, level_num + 1)
return tree
return level_helper(tree, 1)

Write a function that will return a list of paths from leaf to root where the leaf value is equal to val. Each path should be represented as a linked list.
def paths(tree, val):
>>> t = Tree(1, [Tree(2, [Tree(3), Tree(5)]), Tree(7, [Tree(4, [Tree(3)])])])
>>> paths(t, 3)
path_list= []
def paths_helper(tree, path):
if t.is_leaf() and t.label == val:
else:
for branch in t.branches:
return path_list

Write out a function that will take in a list of unique values and create a binary search tree out of it.
def make_bst(lst):
>>> lst = [8, 5, 3, 9]
>>> make_bst(lst)
BTree(8, BTree(5, BTree(3)), BTree(9))
if lst == []:
return BTree.empty
label = lst
if len(lst) == 1:
return BTree(label)
less, greater = [], []
for elem in lst:
if elem > label:
greater.append(elem)
else:
less.append(elem)
left = make_bst(less)
right = make_bst(greater)
return BTree(label, left, right)

Write out a function that will take in a sorted list of unique elements and create a balanced binary search tree out of it. You may want to define the given function, find_median_index to help you.
def make_balanced_bst(sorted_lst):
>>> lst = [1, 2, 3, 4, 5, 6, 7]
>>> make_balanced_bst(lst)
BTree(4, BTree(2, BTree(1), BTree(3)), BTree(6, BTree(5), BTree(7)))
if sorted_lst == []:
return BTree.empty
else if len(sorted_lst) == 1:
return BTree(sorted_lst)
median_index = find_median_index(sorted_lst)
label = sorted_lst(median_index)
left = make_balanced_bst(sorted_lst[:median_index])
right = make_balanced_bst(sorted_lst[median_index + 1:])
return BTree(label, left, right)
def find_median_index(lst):
return len(lst) // 2