Trees, Mutation, Nonlocal

annietang@berkeley.edu�anniewtang.github.io/cs61a

links.cs61a.org/annie-disc

Trees!

Super important, and recurring!

(also recursive)

BUT FIRST . . .

a meme :—)

Terminology

• root: v top of ur tree

• branch node: node w/a parent
• previously known as “child”
• each “child”/branch node can only have one parent

• parent node: node w/branches
• can have multiple branches

• branches down; root is at top and leaves are at bottom

• label: value inside of the node

• leaf: node w/no branches

branches: the subtree that extends from the branch node

Terminology

• height: depth of the furthest/lowest leaf
• aka, maximum depth in the tree!

• depth: # of edges from root of tree to the node
• think: how many edges in the path from root -> node X?

Trees are an Abstract Data Type

(a Concept™ that you choose the implementation for)

Implementation

def tree(label, branches=[]):� # returns a Tree of some form

• Selectors
• how do you grab/extract information from this ~tree~ you’ve just created, without knowing the implementation details?

• Constructors
• how would you create a tree, using only the knowledge/information of what a tree contains? (labels & branches)
• think of the domain (input) and abstracted range (expected output)

ABSTRACTION!!

Implementation

def label(tree):� # returns the label of your root node in the Tree�def branches(tree):� # returns the branches in your Tree�def is_leaf(tree):� # tells you if a node is a leaf or not

​

​

• Selectors
• how do you grab/extract information from this ~tree~ you’ve just created, without knowing the implementation details?

ABSTRACTION!!

Tree Construction Practice

• How would you represent this tree using the constructor given?

Tree(1, [Tree(3,� [Tree(4), � Tree(5), � Tree(6)]),

Tree(2)])

Why Recursion?

• Remember we said tree recursion is good for when you have many cases/pathways you want to cover.
• Lends very naturally to use tree recursion for recursion on trees, because trees themselves have different pathways (i.e. branches) that you want to explore, most likely.
• Remember the “decision tree” that I drew out to illustrate tree recursion (i.e. recursion by “case”) — very similar problem solving strategies for actual trees!
• Recursion → always consider domain and range.
• what input does your function take in (i.e. a string? number? tree?)
• what output does your function give? (i.e. total length? another tree?)

Why Recursion? (pt2)

• Remember branches themselves are subtrees.
• Therefore, if we used recursion on each of our branches, we know that it’s a valid input/domain, since our function is supposed to operate on trees.
• Given that our input is valid, what (in english, conceptually) is our function supposed to return relative to the tree (i.e. “branch”) that is passed in?
• How can we use that output to solve our entire problem at hand?

Practice Problem 3.2

• Define a function tree max(t) that returns the largest number in a tree.
• abstract(!!) away details
• instead of thinking: “I have to check all the nodes”, how does abstract make this problem more simple?
• a tree has one root, and many branches (which are also subtrees)
• what does it mean to make a recursive call on the branches?
• what does that return? why is that useful? how can you use it?

def tree_max(t):

​

​

return max([label(t)] + [tree_max(b) for b in branches(t)]

use RECURSION!

3.2, 3.3

3.3 square(t)

• squaring a number isn’t defined for you
• is it necessary to define one? why or why not?
• you’re squaring all the nodes in the tree, but how to apply abstraction?

3.2: height(t)

• what is the base case (most simple input)
• what happens with that simple input?
• what is the definition of “height”?
• what is abstractable?
• remember branches are subtrees

discuss w/your neighbors!

3.4: find_path(tree, x)

• base case: what is the most simple scenario you’d have?
• immediate success/failure case
• what do you do, if you reach this immediate success/failure
• recursive call: what does calling find_path(tree, x) return?
• if you gave it a branch, what would find_path(branch, x) return?
• using the result of the recursive call
• using abstraction, and what you know find_path should return
• if labels are unique, can you find more than one valid path?
• how can you tell if a path is valid or not? (i.e. contains x or not)
• if you do find a valid path using your recursive call, how do you use the result to accomplish your final goal?
• what did you make that call on, and what does that represent?

discuss w/your neighbors!

Nonlocal

General Idea

• remember that lookup only allows you to look at the value of a binding from a prev frame
• you cannot modify it
• but !! now with nonlocal, you can!
• once you put the keyword “nonlocal” in front of a <name>
• python searches for the first time it was bound in the current environment (excluding the global frame)
• makes a note that in the future, whenever you refer to <name>, you’ll be referring to the previously bound name!

Things to Remember

1. nonlocal does not refer to globally declared variables
1. remember: search for the first binding in your env, �excluding the global frame
2. you cannot override a variable in the current frame with nonlocal
• python does not allow for the same name to have different scopes with the same frame
• nonlocal must refer to a name that exists in a previous frame

Mutable Lists

General Idea

• there are some objects in Python that are mutable
• example: lists, dictionaries!
• you can index into a list to change its contents
• lst[2] = 3
• same with dictionaries!
• dict[“key”] = new_value
• you’re replacing the value in the same list/dictionary
• you’re not creating a new dictionary or list object each time you want to change/modify it
• simply mutating the previously existing one

General Idea

• there are some objects in Python that are mutable
• example: lists, dictionaries!
• you can index into a list to change its contents
• lst[2] = 3
• same with dictionaries!
• dict[“key”] = new_value
• you’re replacing the value in the same list/dictionary
• you’re not creating a new dictionary or list object each time you want to change/modify it
• simply mutating the previously existing one

Have some box-and-pointer diagrams.

Motivation

why we do this thing

• standard, visual way to represent certain data types (lists, tuples, linked lists, pairs, etc.)
• helps you to keep track of the behavior of mutable objects

How to draw these things!!??

• similar to function definitions, we use pointers to refer to list objects
• name points to the list object
• elements represented by adjacent boxes

optional: label each box with the indice

(!) the arrow points to the object as a whole, not at a specific box!

>>> basic = [1, 2, 3]

​

​

>>> nested = [61, [‘a’], ‘!’]

Q: what do nested lists look like?

A: “nested” pointer!!

​

1

2

3

basic

61

‘a’

nested

‘!’

Alright, let’s go back to python!

Some pretty nifty functions

• lst.append(element)
• lst.extend(iterable)
• lst.insert(index, element)
• lst.remove(element)
• lst.pop(index)

lst.append(element)

• takes the element passed in, and just sticks the entire thing at the end of the list
• regardless of what type the element is (another list, a primitive value) → lst.append just sticks it at the end
• i.e. lst.append([3]) → lst → [1, 2, [3]]
• i.e. lst.append(4) → lst → [1, 2, [3], 4]
• returns Nothing

lst = [1. 2]

lst.extend(iterable)

• takes in a iterable and puts the contents of that iterable at the end of the list
• you can think of it like taking away the outer brackets, and sticking whatever is inside at the end of the list
• lst.extend([3]) → tacks on 3 at the end
• lst → [1, 2, 3]
• lst.extend([[4]]) → tacks on [5] at the end
• lst → [1, 2, 3 [4]]
• returns Nothing

lst = [1. 2]

brief interlude: extend vs. append

brief interlude 2: += vs. =

• extend: extending the list with the contents of another list
• append: appending some element directly to the list

also, += is the same as extend!

​

​

​

• += mutates
• = makes a copy, always
• lst += [3] is not the same behavior as lst = lst + [3]
• box and pointer diagrams make this clear!

lst.insert(index, elem)

• inserts an element at given index
• does not replace an element
• just insertion!!
• what happens if you insert at an index that is “out of bounds/range”?
• python just puts it at the end of your list!
• lst.insert(10, 3)
• lst → [1, 2, 3]
• returns Nothing

lst = [1. 2]

lst.remove(element)

• removes the first occurrence of element in list
• otherwise, if element not in list → Error!
• i.e. lst.remove(3) → Error.
• i.e. lst.append(1) → lst → [1, 2, 1]
• i.e. lst.remove(1) → lst → [2, 1]
• returns Nothing

lst = [1. 2]

lst.pop(index)

• default index = -1

i.e. will remove last element if you just do .pop()

>>> lst.pop()�2�>>> lst�[1]

​

• returns popped elem!

• otherwise, pop off element at given index

>>> lst.extend([2, 3])�>>> lst�[1, 2, 3]�>>> lst.pop(1)�2�>>> lst�[1, 3]

​

lst = [1. 2]