Class Notes
(810,487)

Canada
(494,138)

University of Toronto St. George
(42,836)

Computer Science
(745)

CSC148H1
(92)

Paul Gries
(18)

Lecture

# feb15c.docx

Unlock Document

University of Toronto St. George

Computer Science

CSC148H1

Paul Gries

Winter

Description

size
1. def size(root):
2. ‘’’(BSTNode) -> int
3. Return the number of nodes in root’’’
4. if not root:
5. return 0
6. else
7. return 1 + size(root.right) + size(root.left)
sum
1. def sum(root):
2. ‘’’(BSTNode) -> int
3. Return the sum of the nodes in root’’’
4. if not root:
5. return 0
6. else
7. return root.value + sum(root.right) + sum(root.left)
height
1. def height(root):
2. ‘’’(BSTNode) -> int
3. Return the height of tree at root’’’
4. if not root:
5. return 0
6. else
7. return max(height(root.left), height(root.right)) + 1
largest
1. def largest(root):
2. ‘’’(BSTNode) -> int
3. Return the largest key in the tree rooted at root.
4. Precondition: root is not None.'''
5. if not root.right:
6. return root.key
7. else:
8. return largest(root.right)
smallest
o a largest following this method also works
1. def smallest(root):
2. ‘’’(BSTNode) -> int
3. while root.left:
4. root = root.left
5. return root.value
contains
o search all nodes
9. def contains(root, v):
10. ‘’’(BSTNode, object) -> local
11. Return wheather v is a value in the tree rooted at r’’’
12. if not root:
13. return False
14. else
15. return (root.value == v) or contains(root.left, v) or contains(roo

More
Less
Related notes for CSC148H1