QZ03 topics

  1. L9 - Trees
    • Understand tree terminology
      • Parent
      • Child
      • Arity
      • Height
        • Min number of nodes in BT of height h
        • Max number of nodes in BT of height h
      • Root
      • Leaf
      • Node
      • Edge
      • Path
      • Depth
      • Traversal
        • Depth-first
          • Pre-order
          • In-order
          • Post-order
        • Breadth-first
        • Be able to determine a traversal given a tree
        • Know how to implement depth-first/breadth-first, be able to recognize code for it
        • Understand how traversals relate to recursive function calls
  2. L10 - BST
    • BST definition, invariants
    • BST code structure
    • BST subset of BT
    • #nodes and height of perfect tree
    • BST operations
      • Be able to do this by hand
      • contains
      • insert
        • Each inserted element becomes a leaf
        • Does insertion order matter?
      • remove
        • For simple cases or the 2-children case
      • findMin/findMax
    • In-order traversal creates sorted sequence
    • Given two BST’s with same elements (but not structure), which traversal(s) will result in the same sequence?
    • Given a BST, if I do this type of traversal and insert in that order, will I get the same BST?
  3. L11 - BST, cont.
    • BST sort
    • TBD
  4. EX05
    • May ask a question about EX05
  5. Cumulative in that I expect you to remember basic concepts