Class8.md

Class 8: Wednesday, April 5 – Trees

Topics:

• tree, terminology
• binary search tree, operations

Resources:

• review Make School's tree slides
• watch Make School's tree video lecture
• play with VisuAlgo's interactive binary search tree visualization

Challenges:

• implement BinaryNode class with the following properties and instance methods using binary search tree starter code:
  • data - the node's data
  • left - the node's left child, if any
  • right - the node's right child, if any
  • is_leaf - check if the node is a leaf (has no children)
  • is_internal - check if the node is internal (has at least one child)
• implement BinarySearchTree class using BinaryNode objects with the following properties and instance methods using binary search tree starter code:
  • size - property that tracks the number of nodes in constant time
  • is_empty - check if the tree is empty
  • insert(data) - insert a new node with data in order in the tree
  • search(data) - check if a node with data is present in the tree
  • delete(data) - remove the node with data from the tree
• run pytest test_binarysearchtree.py to run the binary search tree unit tests and fix any failures
• annotate all class instance methods with running time complexity analysis

Stretch Challenges:

• implement TreeMap class (map/dictionary abstract data type implemented with binary search tree data structure)
• implement binary search tree with singly linked list nodes instead of binary tree nodes

Project:

• trees and mazes tutorial on Make School's Online Academy