from bt import BTNode
def count(t):
''' (BTNode) -> int
Return the number of nodes in BTNode t.
>>> tree = BTNode(5)
>>> count(tree)
1
>>> b = BTNode(8)
>>> b = insert(b, 4)
>>> b = insert(b, 2)
>>> b = insert(b, 6)
>>> b = insert(b, 12)
>>> b = insert(b, 14)
>>> b = insert(b, 10)
>>> count(b)
7
'''
if not t:
return 0
elif not t.left and not t.right:
return 1
else:
return count(t.left) + count(t.right) + 1
def height(t):
''' (BTNode) -> int
Return the number of nodes in longest path in BTNode t.
>>> tree = BTNode(23)
>>> height(tree)
1
>>> b = BTNode(8)
>>> b = insert(b, 4)
>>> b = insert(b, 2)
>>> b = insert(b, 6)
>>> b = insert(b, 12)
>>> b = insert(b, 14)
>>> b = insert(b, 10)
>>> height(b)
3
'''
if not t:
return 0
elif not (t.left or t.right):
return 1
else:
left_node = height(t.left) + 1
right_node = height(t.right) + 1
return max([left_node, right_node])
def leaf_count(t: BTNode) -> int:
''' (BTNode) -> int
Return number of leaf nodes in BTNode t.
>>> tree = BTNode(17)
>>> leaf_count(tree)
1
>>> b = BTNode(8)
>>> b = insert(b, 4)
>>> b = insert(b, 2)
>>> b = insert(b, 6)
>>> b = insert(b, 12)
>>> b = insert(b, 14)
>>> b = insert(b, 10)
>>> leaf_count(b)
4
'''
if not t:
return 0
elif not (t.left or t.right):
return 1
else:
return leaf_count(t.left) + leaf_count(t.right)
def insert(node, data):
''' (BTNode, object) -> BTNode
Insert data in BST rooted at node if necessary, and return new root.
>>> b = BTNode(5)
>>> b1 = insert(b, 3)
>>> print(b1)
5
3
<BLANKLINE>
'''
return_node = node
if not node:
return_node = BTNode(data)
elif data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
else: # nothing to do
pass
return return_node
if __name__ == '__main__':
import doctest
doctest.testmod()