1 of 38

Mutable Trees

Tuesday, 7/21

2 of 38

Announcements

Congratulations to the winners of the Hog contest!

17 entries in total
Third: Minsu Kim (12 – 4, 62%)
Second: Boyuan Yu (12 – 4, 71%)
First: Evin Yang (15 – 1, 76%)

Project 1 composition revisions due Thursday, 7/23
Homework 7 due Saturday, 7/25
Project 3 due next Tuesday, 7/28
Midterm 2 is next Thursday, 7/30

Fill out alternate exam request form by Thursday 7/23

One-on-one tutoring

If you would like to get one-on-one tutoring, please fill out this form
Small group tutoring is still available
See Piazza for more details

3 of 38

Review: Linked List

Define a function link_extend that extends a linked list mutatively. It takes in two linked lists, s1 and s2.

It should add a copy of s2 to the end of s1, such that if any changes to s2 are made after, s1 will not change.

def link_extend(s1, s2):� """

Mutatively extend s1 with s2

>>> s1 = Link(1)

>>> s2 = Link(2)

>>> link_extend(s1, s2)

>>> s2.rest = Link(3)

>>> print_link(s1)

<1 2>

"""

class Link:� empty = ()�� def __init__(self, first, rest=empty):� assert rest is Link.empty or isinstance(rest, Link)� self.first = first� self.rest = rest

4 of 38

Review: Linked List

def link_extend(s1, s2):� """

Mutatively extend s1 with s2

>>> s1 = Link(1)

>>> s2 = Link(2)

>>> link_extend(s1, s2)

>>> s2.rest = Link(3)

>>> print_link(s1)

<1 2>

"""

if s2 is Link.empty:

return

elif s1.rest is Link.empty:

s1.rest = Link(s2.first)

link_extend(s1.rest, s2.rest)

else:

link_extend(s1.rest, s2)

5 of 38

Review: Linked List

def link_extend(s1, s2):� """

Mutatively extend s1 with s2

>>> s1 = Link(1)

>>> s2 = Link(2)

>>> link_extend(s1, s2)

>>> s2.rest = Link(3)

>>> print_link(s1)

<1 2>

"""

while s1.rest is not Link.empty:

s1 = s1.rest

while s2 is not Link.empty:

s1.rest = Link(s2.first)

s1 = s1.rest

s2 = s2.rest

6 of 38

Trees

Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

7 of 38

Tree class: Terminology

node: a single unit in a tree; contains an entry
root: node at the top of the tree
subtree: a smaller tree within the whole tree
leaf: a node with no children

9

4

5

2

8

3

6

1

9

node

entry

root

subtree

leaf

8 of 38

Tree class

class Tree:

def __init__(self, entry, subtrees=[]):

self.entry = entry

self.subtrees = list(subtrees)

def is_leaf(self):

return not self.subtrees

def tree(entry, subtrees=[]):

...

def entry(t):

...

def subtrees(t):

...

def is_leaf(t):

return not subtrees(t)

3

4

2

1

>>> t = Tree(3, [Tree(2, [Tree(1)]), Tree(4)])

>>> t.entry

3

>>> t.subtrees[0].entry

2

>>> t.subtrees[0].subtrees[0].is_leaf()

True

9 of 38

Tree class: Verifying inputs

class Tree:

def __init__(self, entry, subtrees):

for s in subtrees:

assert isinstance(s, Tree), 'each subtree must be a Tree'

self.entry = entry

self.subtrees = list(subtrees)

Each subtree must be a Tree

>>> t = Tree(1, [2, 3])

AssertionError

>>> t = Tree(1, [Tree(2), 3])

AssertionError

>>> t = Tree(1)

10 of 38

Trees

Terminology (review)
Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

11 of 38

Mutation

Instance variables can be reassigned

Tree can be changed (mutated) after creation

>>> t.subtrees.append(Tree(4))

>>> t.entry = 3

>>> t = Tree(1, [Tree(2)])

4

1

2

3

12 of 38

Trees

Terminology (review)
Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

13 of 38

tree_contains: No mutation

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

Implement tree_contains(t, e):

t is a tree
e is an object

Returns True if e is an element in t
Review of tree processing

No mutation in this example

Use recursion!

14 of 38

tree_contains: Base case

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

Step 1: Base case(s)
Simplest input for e

When e is equal to the entry
Immediately know t contains e

15 of 38

tree_contains: Base case

Step 1: Base case(s)
Simplest input for t

When t is a leaf

Already know e is not entry
e can’t be in subtrees (no subtrees in a leaf)
t does not contain e

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif t.is_leaf():

return False

16 of 38

tree_contains: Base case

Step 2: Recursive call
How to reduce the input?

Move to a single subtree

What does tree_contains of a subtree do?

Check if e is contained in the subtree

How does this help?

If e is in the subtree, e is in the overall tree

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif t.is_leaf():

return False

9

4

5

2

8

3

6

1

17 of 38

tree_contains: Base case

Step 3: Using recursive calls
If e is contained in a subtree, return True
If e is not contained in any subtree, return False

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif t.is_leaf():

return False

else:

for s in t.subtrees:

if tree_contains(s, e):

return True

return False

9

4

5

2

8

3

6

1

18 of 38

tree_contains: Using list comprehensions

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif t.is_leaf():

return False

else:

return any([tree_contains(s, e)

for s in

t.subtrees])

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif t.is_leaf():

return False

else:

for s in t.subtrees:

if tree_contains(s, e):

return True

return False

Built-in any function returns True if any elements in list are True
More concise, but either solution is fine

Using any is also less efficient (why?)

19 of 38

tree_contains: Even more concise!

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif t.is_leaf():

return False

else:

return any([tree_contains(s, e)

for s in

t.subtrees])

def tree_contains(t, e):

"*** YOUR CODE HERE ***"

return e == t.entry or \

any([tree_contains(s, e)

for s in

t.subtrees])

Want to check if e == t.root regardless of if t is a leaf or not
If no subtrees, list comprehension will be empty
any([ ]) returns False
“t contains e if e is t’s root or if any of t’s subtrees contain e”

20 of 38

tree_contains: Runtime

Intuitively, need to compare each entry to e

Linear in number of nodes

Let n be the number of nodes in t
One recursive call per node; n nodes implies O(n) calls

Each call uses == and is_leaf()
Each recursive call takes O(1) time

Total: O(n) runtime

O(1)

21 of 38

Trees

Terminology (review)
Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

22 of 38

tree_map

def tree_map(t, fn):

"*** YOUR CODE HERE ***"

Implement tree_map(t, fn):

t is a tree
fn is a function

Applies fn on each element of t

Mutate t

No return value
Use recursion!

23 of 38

tree_map

def tree_map(t, fn):

"*** YOUR CODE HERE ***"

if t.is_leaf():

t.entry = fn(t.entry)

Step 1: Base case
Simplest input for t

When t is a leaf

What does tree_map do on a leaf?

Apply fn on leaf's entry
Mutate: reassign t.entry

24 of 38

tree_map

def tree_map(t, fn):

"*** YOUR CODE HERE ***"

if t.is_leaf():

t.entry = fn(t.entry)

Step 2: Recursive call
How to reduce the input?

Move to a single subtree

What does tree_map of a subtree do?

Applies fn on elements in that subtree

How does this help?

Use recursive call to apply fn on all subtrees

25 of 38

tree_map

def tree_map(t, fn):

"*** YOUR CODE HERE ***"

if t.is_leaf():

t.entry = fn(t.entry)

else:

t.entry = fn(t.entry)

for s in t.subtrees:

tree_map(s, fn)

Step 3: Using recursive calls
Apply fn on entry

Mutate (reassign t.entry)

Apply fn on each subtree
No return value (as stated in the problem)

26 of 38

tree_map

def tree_map(t, fn):

"*** YOUR CODE HERE ***"

if t.is_leaf():

t.entry = fn(t.entry)

else:

t.entry = fn(t.entry)

for s in t.subtrees:

tree_map(s, fn)

def tree_map(t, fn):

"*** YOUR CODE HERE ***"

t.entry = fn(t.entry)

for s in t.subtrees:

tree_map(s, fn)

Reassign t.entry = fn(t.entry) regardless of if t is a leaf

Don't need the if/else statement

27 of 38

tree_map

Intuitively, need to apply fn on each entry

Linear in number of nodes

Let n be the number of nodes in t
One recursive call per node; n nodes implies O(n) calls

Each call uses fn
Runtime of fn is independent of n
fn takes O(1) with respect to n

Total: O(n) runtime

O(1)

28 of 38

Trees

Terminology (review)
Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

29 of 38

Binary trees: Definition

Binary tree: each node has at most two subtrees

9

4

5

2

8

3

6

1

Not binary tree

5

3

2

7

4

8

1

Binary tree

5

2

1

7

4

8

3

Binary tree

30 of 38

Binary trees: Class

At most two subtrees

Labeled “left” and “right”

What if a subtree is missing?

Label it an “empty Tree”

class BinaryTree:

empty = ()

def __init__(self, entry, left=empty, right=empty):

self.entry = entry

self.left = left

self.right = right

BinaryTree(3,

BinaryTree(2,

BinaryTree(1)),

BinaryTree(4,

BinaryTree.empty,

BinaryTree(3)))

31 of 38

Trees

Terminology (review)
Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

Recursive tree

32 of 38

Binary trees: Definition

Binary search tree: a binary tree with the following properties:

Elements left of a node are smaller than or equal to its entry
Elements right of a node are larger than or equal to its entry

9

4

5

2

8

3

6

1

Not binary search tree

5

3

2

7

4

8

1

Not binary search tree

5

2

1

7

4

8

3

Binary search tree

33 of 38

Trees

Terminology (review)
Tree class

Mutation
tree_contains
tree_map

Binary trees

Binary search trees
bst_contains

34 of 38

bst_contains

def bst_contains(t, e):

"*** YOUR CODE HERE ***"

Implement bst_contains(t, e):

t is a tree
e is an object

Returns True if e is an element in t
How is this different from tree_contains?

35 of 38

bst_contains: Base case

def bst_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

Step 1: Base case(s)
Similar to tree_contains
If e equals the entry, return True
We'll come back to the other base case...

36 of 38

bst_contains: Recursive cases

def bst_contains(t, e):

"*** YOUR CODE HERE ***"

if e == t.entry:

return True

elif e < t.entry:

return bst_contains(t.left, e)

else:

return bst_contains(t.right, e)

Step 2 + 3: Recursive case
Difference between tree and binary search tree?
Everything left of root is smaller than root

If e is smaller than root, e can only be in left subtree

Similar for e larger than root

5

2

1

7

4

8

3

37 of 38

bst_contains: Base case (revisited)

def bst_contains(t, e):

"*** YOUR CODE HERE ***"

if t is BinaryTree.empty:

return False

elif e == t.entry:

return True

elif e < t.entry:

return bst_contains(t.left, e)

else:

return bst_contains(t.right, e)

What if t.left (or t.right) is BinaryTree.empty?
Need another base case
Is e contained in an empty tree?

No: nothing is in an empty tree

5

7

8

38 of 38

bst_contains: Runtime

Don't need to check every node

Less than linear?

Let n be the number of nodes in t
If tree is balanced:

Each recursive call reduces size of input by (roughly) half
O(log n) runtime

If tree is unbalanced:

Each recursive call reduces size of input by a constant factor
O(n) runtime

5

2

1

7

4

8

6

5

3

4

6