CSC148 - Tree method practice

Here is an abbreviated version of the Tree class we’re studying this week.

class Tree:
_root: Any | None
_subtrees: list[Tree]

def __init__(self, root: Any | None, subtrees: list[Tree]) -> None:

def is_empty(self) -> bool:

Your goal for this worksheet is to implement the following new Tree method, using the recursive Tree code template.

class Tree:
def leaves(self) -> list:
"""Return a list of all of the leaf values in this tree.
"""
if self.is_empty():
...
elif self._subtrees == []: # self is a leaf
...
else:
...
for subtree in self._subtrees:
... subtree.leaves() ...
...

1. (base cases, examples) First, let’s consider some base cases for this function. In the space below, write two doctest examples,
one that calls this method on an empty tree, and one that calls this method on a leaf.

>>> t = Tree(None,[])
>>>t.leaves()
>>>[]
>>>t = Tree(3,[])
>>>t.leaves()
>>>[3]

2. (base cases, implementation) Implement the base cases of the Tree.leaves method below.

class Tree:
def leaves(self) -> list:
"""Return a list of all of the leaf values in this tree.

The leaf values are returned in left-to-right order.

"""
if self.is_empty():
return 0

elif self._subtrees == []: # self is a leaf

return [self._roots]

else:
... # Will do this later
3. (recursive step, example) Now suppose we have a variable
tree that refers to the tree on the right.

(a) Complete the doctest example below.

>>> tree.leaves()
>>> [3,2,6,10,111]

(b) Complete the following recursion table to show each of the subtree subtree.leaves()
subtrees of this tree, as well as what the recursive call to
leaves will return for that subtree, assuming the recur-
sive call is correct. We have started the table for you.

[3,2,6]

[10]

[111]

4. (recursive step, implementation) Implement the recursive step for the Tree.leaves method.

class Tree:
def leaves(self) -> list:
... if self.is_empty():
else: # Recursive step! return []
record = [] elif self._subtrees == []:
for subtrees in self._subtrees: return [self._roots]
record.extend(subtrees.leaves()) else:
return record leaves = []
for subtrees in self._subtrees:
leaves.extend(subtrees.leaves())
return leaves

5. Recall that in many Tree methods, the “leaf” case from our recursive code template is redundant and can be removed. Is
this the case here? Why or why not?
why can’t. Since the leaf case in this one is the important case. We care about leafs in particular.
 CSC148 - Tree Deletion Algorithms
We’ve seen that when deleting an item from a tree, the bulk of the work comes when you’ve already found the item, that is, you
are “at” a subtree where the item is the root value, and you need to delete it. Our goal is to complete our code from lecture by
implementing the helper Tree.delete root.
difference between empty tree and leaf:
class Tree: empty tree: _root is None, _subtrees is []
def delete_root(self) -> None: leaf: _root is not None, _subtrees is []
"""Remove the root of this tree. Precondition: not self.is_empty()"""

1. We can’t just set the self. root attribute to None. Why not?

may contradicts the representation invariants. We cannot have_root is None but _subtrees is
not empty list.
Instead, we will give root a new value from somewhere else in the tree. Let’s look at two di↵erent ways we can do this.

2. Approach 1: “Promote” a subtree

Idea: to delete the root, take the rightmost subtree t1 , and make the root of t1 the new root of the full tree, and make the
subtrees of t1 become subtrees of the full tree. (Note: we could have promoted the leftmost subtree, or any other subtree.)

Figure 1: Before and after images of Tree.delete root using Approach 1.

Implement Tree.delete root using this approach.

class Tree:
def delete_root(self) -> None:
"""Remove the root of this tree. Precondition: not self.is_empty()"""
new_node = self._subtrees[-1]._roots
update_sub = self._subtrees[-1]._subtrees
self._roots = new_node
for items in uodate_sub:
self._subtrees.append(Tree(new_node, [item]))

tmp = self._subtrees.pop()
self._root = tmp._root
self._subtrees.extend(tmp._subtr
ees)
3. Approach 2: Replace the root with a leaf
Idea: to delete the root, find the leftmost leaf of the tree, and make the leaf value the new root value. No other values in
the tree should move. (Note: we could have replaced the root with the value in rightmost leaf, or any other leaf.)

Figure 2: Before and after images of Tree.delete root using Approach 2.

Implement Tree.delete root using this approach. We recommend defining an additional helper method to recursively
remove and return the leftmost leaf in a tree.

class Tree:
def delete_root(self) -> None:
"""Remove the root of this tree. Precondition: not self.is_empty()"""

if self._subtrees == []:
done
else:
goal = self._subrees[0]

self._root = self._extract_leaf()

def _extract_leaf() -> Any:

if not self._subtrees : #at at a leaf
root, self._root = self._root, None the left most leaf may not exists
return root ???
else:
root = self._subtrees[0]._extract_leaf()
if self._subtrees[0].is_empty:
self._subrees.pop() #remove it from the left
return root
 CSC148 - Trees and Nested Lists
We can represent any tree as a nested list, where the first sub-nested-list is the root of the tree, and every other sub-nested-list
is the nested list representation of one of the tree’s subtrees. The nested list representation of an empty tree is simply the empty
list. The nested list representation of a tree with a single item x is [x].

1. Here’s a bigger tree:

Its nested list representation is:

['A', ['B', ['E'], ['F']], ['C', ['G'], ['H', ['J']]], ['D', ['I']]]

Match the opening and closing brackets, and then make sure you see the correspondence between this nested list and the
tree above.
2. Follow the recursive design recipe to write the method Tree.to nested list, which returns the nested list representation
of the tree.
Reminder : for the recursive step, before writing any code, it’ll be useful to draw a tree with around three subtrees, and
for each, to write the expected return value when we recurse on that subtree.

def to_nested_list(self) -> List :

if self.is_empty():
return []

is self._subtrees == []:
return [self._root]
else:
nest_list = []
nest_list.append(self._root) nest_list = [self._root]
for subtree in self._subtrees:
nest_list.append(subree.to_nested_list)
return nest_list
3. In our nested list representation of a tree, we require that the first sub-nested-list is not a list, but instead a simple type
like an integer or string — something that can be the root value for a tree. This means that while every tree has a nested
list representation, not every nested list is a valid representation of a tree. Create a small nested list that is not a valid
representation of a tree. Try to make a tree out of your nested list, and observe the problem with doing so.

[[‘A’], [‘B’, [‘C’], [‘D’]]]

4. Next, follow the recursive design recipe to implement the top-level function to tree, which takes a nested list and returns
the tree that it represents, or None if the given nested list is not a valid representation of a tree.
Note that the only Tree method you should need to use here is the initializer. And since to tree is a top-level function,
you should not access the private instance attributes of Tree objects.

def to_tree(iterm : nested list) -> Tree:

if len(item) == 0: see picture

return Tree(None, [])
elif len(item) == 1:
if not isinstance(item[0], list):
return Tree(item[0], [])
if isinstance(obj,int):
else:
return None
return None
else:
else:
#empty tree vs non-empty tree
if obj == []:
return Tree(None, [])
root = obj[0]
#Make sure this is a list
if isinstance(root, list):
return None
subtrees = []
for sublist in obj[1:]:
subtree = to_tree(sublist)
if subtree is None:
return None
subtrees.append(subree)
return Tree(root, subtrees)