Sunday 15 March 2015

Adapting in_between() for Binary Search Trees


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.


No comments:

Post a Comment