Class8.md

Class 8: Trees & Binary Search Trees

Minute-by-Minute [OPTIONAL]

NOTE: Fill in with the appropriate items

Elapsed	Time	Activity
0:00	0:05	Objectives
0:05	0:15	Overview
0:20	0:45	In Class Activity I
1:05	0:10	BREAK
1:15	0:45	In Class Activity II
TOTAL	2:00

Learning Objectives (5 min)

NOTE: Fill in with the appropriate items

By this end of this lesson, students should be able to...

1. Explain a basic tree data structure and what the use cases for one are
2. Implement a binary search tree

Topics

• Tree data structure, terminology
• Binary search tree, operations

Resources

• Review Make School's trees slides
• Watch Make School's trees video lecture
• Read Interview Cake's articles on logarithms and binary search and binary tree properties
• Read Vaidehi Joshi's articles on trees and their properties and binary search trees with beautiful drawings
• Watch HackerRank's trees and binary search tree video (up to 3:00)
• Watch Harvards's family trees and binary search tree video and stack frames video
• Play with VisuAlgo's interactive binary search tree visualization

Challenges

• Implement BinaryTreeNode class with the following properties and instance methods using binary tree starter code:
  • data - the node's data element
  • left - the node's left child, or None (if it does not exist)
  • right - the node's right child, or None (if it does not exist)
  • is_leaf - check if the node is a leaf (an external node that has no children)
  • is_branch - check if the node is a branch (an internal node that has at least one child)
  • height - return the node's height (the number of edges on the longest downward path from the node to a descendant leaf node)
• Implement BinarySearchTree class (using BinaryTreeNode objects) with the following properties and instance methods using binary tree starter code:
  • root - the tree's root node, or None (if the tree is empty)
  • size - property that tracks the number of nodes in constant time
  • is_empty - check if the tree is empty (has no nodes)
  • height - return the tree's height (the number of edges on the longest downward path from the tree's root node to a descendant leaf node)
  • contains(item) - return a boolean indicating whether item is present in the tree
  • search(item) - return an item in the tree matching the given item, or None if not found
  • insert(item) - insert the given item in order into the tree
• To simplify the contains, search, and insert methods with code reuse, implement iterative and recursive tree search helper methods:
  • _find_node_iterative(item) - return the node containing item in the tree, or None if not found
  • _find_node_recursive(item) - return the node containing item in the tree, or None if not found
  • _find_parent_node_iterative(item) - return the parent of the node containing item (or the parent of where item would be if inserted) in the tree, or None if the tree is empty or has only a root node
  • _find_parent_node_recursive(item) - return the parent of the node containing item (or the parent of where item would be if inserted) in the tree, or None if the tree is empty or has only a root node
• Run python binarytree.py to test BinarySearchTree class instance methods on a small example
• Run pytest binarytree_test.py to run the binary tree unit tests and fix any failures
• Write additional unit tests for the BinaryTreeNode and BinarySearchTree classes
  • Add to existing test cases to ensure the size property is correct
  • Include test cases for the height instance method on both classes
• Annotate class instance methods with complexity analysis of running time

Stretch Challenges

• Implement this additional BinarySearchTree class instance method:
  • delete(item) - remove item from the tree, if present, or else raise ValueError (hint: break this down into cases based on how many children the node containing item has and implement helper methods for subtasks of the more complex cases)
• Write additional unit tests for the BinarySearchTree class
  • Include several test cases for the delete instance method covering each case handled by the algorithm
• Implement binary search tree with singly linked list nodes (having only one link to another node) instead of binary tree nodes (having two links to other nodes)