If you need help reviewing Tree ADT, take a look at these resources:
Each question has a "Toggle Solution" button -- click it to reveal that question's solution.
Tree ADT
Recall that we learned two different tree representations in this class:
- Abstract data type (defined in terms of functions). This is what this worksheet covers.
- Object-oriented programming (defined in termes of classes and methods). This will be covered in another review session.
The tree abstract data type is defined in terms of these four functions:
def tree(root, subtrees=[]):
return [root] + list(subtrees)
def root(t):
return t[0]
def subtrees(t):
return t[1:]
def is_leaf(t):
return not subtrees(t)
Since this is an ADT, we don't care so much about the implementation of the constructors and selectors: as long as we know what they do, we can use them.
Remember, trees are recursively defined (trees are constructed using smaller trees). For most questions involving the tree ADT, you can break down the thought process into three steps:
- Base case: Usually, this is if the tree is a leaf (use the
is_leaf
function) - Recursive call: Consider what a recursive call on a single branch will do. What information does it give you?
- Recursive case: Make recursive calls on each branch (using a
for
loop or a list comprehension) and combine that in some way with the root for your final answer.
Question 1
Implement a function contains
, which takes a tree t
and an element
e
. contains
will return True if t
contains the element e
, and
False otherwise.
def contains(t, e):
"*** YOUR CODE HERE ***"
def contains(t, e):
if e == root(t):
return True
elif is_leaf(t):
return False
else:
for b in subtrees(t):
if contains(b, e):
return True
return False
It is possible to use a list comprehension to solve this problem,
thanks to the built-in any
function. The any
function takes a list
of booleans and returns True if any of those booleans is True:
def contains(t, e):
if e == root(t):
return True
elif is_leaf(t):
return False
else:
return any([contains(b, e) for b in subtrees(t)])
While this version is more concise, it is also more inefficient (why?).
Question 2
Implement a function all_paths
, which takes a tree t
. all_paths
will return a list of paths from the root to each leaf. For example,
consider the following tree:
5
/ \
3 6
/ \
2 1
Calling all_paths
on this tree would return
[[5, 3, 2],
[5, 3, 1],
[5, 6] ]
The list contains three paths (each path is itself a list).
def all_paths(t):
"*** YOUR CODE HERE ***"
def all_paths(t):
if is_leaf(t):
return [[root(t)]]
else:
total = []
for b in subtrees(t):
for path in all_paths(b):
total.append([root(t)] + path)
return total
It is possible to solve this using a list comprehension, but the list comprehension gets a little complicated:
def all_paths(t):
if is_leaf(t):
return [[root(t)]]
else:
return [[root(t)] + path for b in subtrees(t)
for path in all_paths(b)]
Notice that the for
statements in the list comprehension are exactly
the same as the two for
loops in the original solution.
Question 3
Implement a function max_tree
, which takes a tree t
. It returns a
new tree with the exact same structure as t
; at each node in the new
tree, the entry is the largest number that is contained in that node's
subtrees or the corresponding node in t
. For example, consider this
tree:
5
/ \
3 6
/ \
2 4
Calling max_tree
will return the following tree:
6
/ \
4 6
/ \
2 4
For example, the largest number that occurs at the root or below it is
6 (i.e. max(5, 3, 2, 4, 6) = 6
), so the root of the new tree is 6.
def max_tree(t):
"*** YOUR CODE HERE ***"
def max_tree(t):
if is_leaf(t):
return tree(root(t))
else:
new_subtrees = [max_tree(b) for b in subtrees(t)]
new_root = max([root(t)] + [root(s) for s in new_subtrees])
return tree(new_root, new_subtrees)