This Week's Worksheet ⬇️

Tree Concept Review

Writing the functions
- Base Case ⇒ when we reach a leaf node
  - if is_leaf(t)
  - if len(branches) == 0
- Recursive case ⇒ passing each branch as an input, haven't reach leaf node
  - for b in branches(t) ...
Abstraction barriers
- label(t) rather than t[0]
- However, branches(t)[0] is allowed! → this is okay since branches returns a list of trees
Empty branches
- tree(5) is the same as tree(5, [])

Tree functions

tree() → constructor

def tree(label, branches=[]): 
		return [label] + list(branches)

branches() → returns a list of trees

def branches(tree):
		return tree[1:]

label() → values are numbers

def label(tree): 
		return tree[0]

Tree Practice Problems

Let t be the tree depicted above. What do the following expressions evaluate to? If the expressions evaluates to a tree, format your answer as tree(... , ...).

Untitled

label(t)
branches(t)[1]
branches(branches(t)[1])[1]

Write the function sum_of_nodes which takes in a tree and outputs the sum of all the elements in the tree.
```
def sum_of_nodes(t): 
	 """
   >>> sum_of_nodes(t) # 4 + 5 + 2 + 1 + 8 + 2 + 1 + 4 = 27
   27
   """
```
Observations:
- (Toggle to check)
Solution:
- (Toggle to check)
1. Write a function, replace_x that takes in a tree, t, and returns a new tree with all labels x replaced with 0.
  
  Observations:
  - (Toggle to check)
  Solution:
  - (Toggle to check)
  1. Write a function, all_paths that takes in a tree, t, and returns a list of paths from the root to each leaf. For example, if we called all_paths(t) on the following tree, all_paths(t) would return [[2, 2], [2, 4, 2], [2, 4, 3]].
```
def all_paths(t): 
		paths = []
		if ________________________________________ 
				_______________________________________
		else: 
				_______________________________________
		        ___________________________________
		            _______________________________
		return paths
```
    Observations:
    - (Toggle to check)
    Solution:
    - (Toggle to check)
Mutation Concept Review

Immutability vs Mutability
- Immutable types: int, float, string, tuple
- mutable types: list, dict
- Mutable inside immutable —> immutable still changes
```
t = (1, [2, 3])
t[1][0] = 99
t[1][1] = "Problems"
```
List Methods
- append(elem) adds elem to the end of the list, return None
- extend(lst) extends the list by concatenating it with lst, return None, cannot extend single element (elem = 1, extend(elem) is incorrect, extend([elem]) is correct)
- insert(i, elem) insert elem at index i, return None
- remove(elem) removes the first occurence of elem in list, otherwise errors, return None
- pop(i) removes the element at index i, default remove the last element of the list. return the element that is removed.
Mutative (destructive) Operations
- lst.append(element)
- lst.extend(lst)
- lst.pop(index)
- lst += lst (Note - this is different than: lst = lst + lst)
- lst[i] = x
Non-mutative (non-destructive) Operations
- lst + lst
- lst * n
- lst[i:j]
- list(lst)
Mutation Practice Problems

https://pythontutor.com/visualize.html#mode=edit
- Line 5: This does nothing because the value of this expression is never assigned to a variable. List slicing creates a copy of a list that is immediately deleted
- Line 7: remove deletes the first element with a given value, so the first instance of 1 is deleted. remove returns None, so the outer call to remove gets rid of the None element of ghost
1. Given some list lst, possibly a deep list, mutate lst to have the accumulated sum of all elements so far in the list. If there is a nested list, mutate it to similarly reflect the accumulated sum of all elements so far in the nested list. Return the total sum of the original lst.
  
  Hint: The isinstance function returns True for isinstance(l, list) if l is a list and False otherwise.
```
def accumulate(lst):
		"""
		>>> l = [1, 5, 13, 4]
		>>> accumulate(l)
		23
		>>> l
		[1, 6, 19, 23]
		>>> deep_l = [3, 7, [2, 5, 6], 9]
		>>> accumulate(deep_l)
		32
		>>> deep_l
		[3, 10, [2, 7, 13], 32]
		"""
		sum_so_far = 0
		for ________________________________________:
				________________________________________ 
				if isinstance(___________________, list):
            inside = ___________________________
						____________________________________ 
				else:
	          ____________________________________
						____________________________________ 
		return ___________________________________
```
  Observations:
  - (Toggle to check)
  Solution:
  - (Toggle to check)