Last week we had the second Term Test, and one of the questions we had involved manipulating a piece of code we had seen in the lab. While I am usually horrible writing recursive code, I have a good time interpreting it. Therefore, today we are going to adapt one of the functions seen in class:
list_between(). We have changed the function a little bit and named it
in_between().
This is the code we are working with:
def in_between(node, start, end): ''' (BTNode, object, object) -> list
Return a Python list of all values in the binary search tree
rooted at node that are between start and end (inclusive).
>>> in_between(None, 4, 11)
[]
>>> b = BTNode(8)
>>> b = insert(b, 6)
>>> b = insert(b, 2)
>>> b = insert(b, 5)
>>> b = insert(b, 11)
>>> b = insert(b, 7)
>>> b = insert(b, 1)
>>> in_between(b, 4, 5)
[5]
>>> L = in_between(b, 6, 11)
>>> L.sort()
>>> L
[6, 7, 8, 11]
'''
#when there is no node
#return an empty list
#alternatively use:
#if node is None:
if not node:
return []
#you need to act recursively,
#gathering numbers from node.data
#while checking if you can go
#further left of further right
else:
#go further left
lst_left = (in_between(node.left, start, end)
if node.data > start
else [])
#go further left
lst_right = (in_between(node.right, start, end)
if node.data < end
else [])
#check on the node lst_node = ([node.data]
if (start <= node.data <= end)
else [])
#join all lists
return lst_left + lst_node + lst_right
Let's say for example you want to do something a bit different. Now you want to search strictly for numbers that are multiples of three. This can be accomplished with a simple addition. What we are going to do is add the condition
node.data % 3 == 0 in the part of the code where the objects are checked for compliance with start and end. Additionally, we are going to change the docstring so that it is strictly for numbers.
This is the modified code:
def threes_in_between(node, start, end):
''' (BTNode, number, number) -> list
Return a Python list of all values in the binary search tree
rooted at node that are between start and end (inclusive),
and are multiples of three.
>>> in_between(None, 4, 11)
[]
>>> b = BTNode(9)
>>> b = insert(b, 6)
>>> b = insert(b, 2)
>>> b = insert(b, 5)
>>> b = insert(b, 11)
>>> b = insert(b, 7)
>>> b = insert(b, 1)
>>> in_between(b, 4, 5)
[5]
>>> L = in_between(b, 6, 11)
>>> L.sort()
>>> L
[6, 9]
'''
#when there is no node
#return an empty list
#alternatively use:
#if node is None:
if not node:
return []
#you need to act recursively,
#gathering numbers from node.data
#while checking if you can go
#further left of further right else:
#go further left
lst_left = (threes_in_between(node.left, start, end)
if node.data > start
else [])
#go further left
lst_right = (threes_in_between(node.right, start, end)
if node.data < end
else [])
#check on the node
lst_node = ([node.data]
if (start <= node.data <= end
and node.data % 3 == 0)
else [])
#join all lists
return lst_left + lst_node + lst_right
So it was a simple change that allowed us to be selective about the data we gather. It is important to notice, too, that lst_node is the only list that gathers data, while the other ones just act recursively on the left and right, deciding where to stop (remember that a Binary Search Tree's data increases to the right and decreases to the left).
Challenges
You might feel inclined to add the condition to lst_right and lst_left, too.
else:
#go further left
lst_left = (threes_in_between(node.left, start, end)
if node.data > start and node.data % 3 == 0
else [])
#go further left
lst_right = (threes_in_between(node.right, start, end)
if node.data < end and node.data % 3 == 0
else [])
However, this would be a huge mistake since their only job is to dig (or climb, since it is a tree) further down the tree with start and end as limits, finally gathering the numbers when lst_node does its magic.
