CP164 Midterm: Imagine that the BST
Imagine that the BST _count attribute is not available, and we wish to count the number of
nodes in the following tree:
Sample BST
We'll define a method called count to perform the node count. Because we are going to use
recursion, we'll need an auxiliary function, which we'll call _count_aux to perform the
actual counting. Both methods are fruitful because clearly we have to return a count value.
The count method is:
def count(self):
"""
---------------------------------------------------------
Returns the number of nodes in a BST.
Use: number = bst.count()
-------------------------------------------------------
Postconditions:
returns
number - count of nodes in tree (int)
----------------------------------------------------------
"""
number = self._count_aux(self._root)
return number
The traversal requires an auxiliary method because the top-level method call does not
allow access to the internal node structure of a BST. The code is:
def _count_aux(self, node):
"""
---------------------------------------------------------
Returns the number of nodes in a BST subtree.
-------------------------------------------------------
Preconditions:
node - a BST node (_BSTNode)
Postconditions:
returns
number - count of nodes in the current subtree (int)
----------------------------------------------------------
"""
if node is None:
# Base case: node does not exist
number = 0
else:
# General case: node exists.
number = 1 + self._count_aux(node._left) + \
self._count_aux(node._right)
return number
The method is very simple and follows the algorithm noted above: check to see if the node
exists, and if it does count that node (1 +), and then call the recursive method on the left
(self._count_aux(node._left)) and right (self._count_aux(node._right)) children.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Imagine that the bst _count attribute is not available, and we wish to count the number of nodes in the following tree: We"ll define a method called count to perform the node count. Because we are going to use recursion, we"ll need an auxiliary function, which we"ll call _count_aux to perform the actual counting. Both methods are fruitful because clearly we have to return a count value. Returns the number of nodes in a bst. Postconditions: returns number - count of nodes in tree (int) number = self. _count_aux(self. _root) return number. The traversal requires an auxiliary method because the top-level method call does not allow access to the internal node structure of a bst. Returns the number of nodes in a bst subtree. Postconditions: returns number - count of nodes in the current subtree (int) if node is none: # base case: node does not exist number = 0 else:
