Trees: Difficult
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)])
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)
[Link(3, Link(2, Link(1))), Link(3, Link(4, Link(7, Link(1))))]
path_list= []
def paths_helper(tree, path):
if ________:
________
else:
________
________
paths_helper(____, ____)
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)
Tree(8, [Tree(5, [Tree(3)]), Tree(9)])
if ______:
return
label = ______
if ______:
return ______
less, greater = ____, ____
for ______:
if ______:
______
else:
______
left = ______
right = ______
return ______
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)
Tree(4, [Tree(2, [Tree(1), Tree(3)]), Tree(6, [Tree(5), Tree(7)])])
if ______:
return
else if ______:
return ______
median_index = find_median_index(______)
label = ______
left = ______
right = ______
return ______
def find_median_index(lst):
return ______