Homework 6 (Spring 2025) - HedgeDoc

<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # Homework 6 - Applications (Spring 2026) **Due: Friday, April 24, 2026 at 11:59 p.m.** # Overview  This semester, we've studied a variety of data structures and how to implement them. But do you really understand their features? Do you really understand how to _use_ them when solving computational problems? We're about to find out! In this assignment, you'll work through a collection of programming problems that engage this semester's data structures in different ways. While you will implement most of your solutions in code, you will also develop plans, examples, and design insights to demonstrate how you understand data structures in the context of these problems. While the solutions to many of these problems are available online, the goal of this assignment is to get you to understand key strategies to working with data structures. Incidentally, **these problems are similar to problems asked during coding interviews, so it's in your best interest to do them on your own!** :::success **Heads up**: While this assignment pushes you to recognize opportunities to use the data structures we have been working with, it's not a summative assessment of your knowledge. **If you struggle with deciding which data structure to use, that's okay**--it doesn't mean you aren't familiar with the course material. **Instead, consider this homework as a brain teaser**, a challenge to push you to think creatively! ::: # Learning Objectives In this assignment, you will: - Apply common data structures to new contexts - Strengthen understanding of time and auxiliary space complexity by developing and optimizing solutions - Create solution plans before implementation - Articulate reasoning for design decisions - Write well-developed test suites # Setup  You can download the stencil code using this **[Github Classroom](https://classroom.github.com/a/3qS5pRHR)** link. :::warning :warning: **Warning**: **Be sure to read the [**Python Stencil Setup Guide**](https://docs.cs200.io/s/python-stencil-setup-guide)** for important instructions on how to set up VSCode to use the stencil. In particular, **make sure you [set up your environment](https://docs.cs200.io/s/python-stencil-setup-guide#Setting-up-your-environment)**--if you don't this, you won't be able to run any tests! :::  **Various other resources you may find helpful** - **[Our Python Stencil setup guide](https://docs.cs200.io/s/python-stencil-setup-guide)**: for how to load the stencil - **[Our guide for going to Python from Java](https://docs.cs200.io/going-to-python-from-java)** which includes links to the Python documentation that you should refer to - **[Our Python Testing Guide](https://docs.cs200.io/s/python-testing-guide)**: how to run and debug tests, as well as this [annotated VSCode debugging guide](https://brown-csci0200.github.io/assets/lectures/23python1/Lec25_whiteboard_f22.pdf) from lecture - **[Our Python Style Guide](https://docs.cs200.io/python-style-guide)**: how to format your Python code # How it works This assignment contains four independent problems, each of which involve working with various data structures. Each problem also has some efficiency requirements in terms of time complexity, auxiliary space complexity, or both. Your goal is to develop a solution to the problem that meets the given complexity requirements. If this sounds challenging, don't worry! **At this point in the course, you have all the conceptual tools you need**, and we provide several planning prompts to get you started thinking about your design before you start writing code. Be sure to read and follow these prompts carefully--they are designed to help you! **How you will be graded?** For each problem, you will be graded in terms of your solution's *correctness* (i.e., does it produce the correct results?) and *performance* (i.e., does it meet the time/space efficiency requirements?). Solutions that are correct but don't meet the efficiency requirements will still receive partial credit. For more information, see [Grading](#Grading). :::success **About space complexity:** For each problem, part of your grade will depend on meeting specific requirements for time and space complexity. For space complexity, we are specifically referring to **auxiliary space complexity**, which is the **extra** space needed to run the solution, and excludes the space for the original input. For example, if you were to use heapsort to sort an input list, the space needed for the heap is auxiliary. It is internal to the computation, not part of the input. ::: **Ready?** Below are 4 problems of varying difficulty. We highly recommend working through each problems' set of tasks *in order*, as they all build on each other. :::success ### :eyes: :sparkles: Ground rules (and helpful resources) :eyes: :sparkles: Some important notes before you get started: - **You won't see any data structures we haven't seen in class before**. You can solve each problem using the concepts and data structures we have seen in CS 200. - The end of this document contains a :sparkles: **[Data structure reference](#Data-Structure-Reference)** :sparkles: : a list of all the data structures we consider fair game, and how to create them in Python. Our stencil provides some data structures for you (Linked Lists and Binary Trees), defined in `classes.py`. Each problem will have more info on these as you need them. - You are not permitted to modify the given data structures in `classes.py`. Instead, your job is to use these data structures, and others from the [Data structure reference](#Data-Structure-Reference)), to solve the problem. - Like most assignments, this assignment is divided into tasks: - **For tasks marked "Code"**: you will add code to either your solution in either `imp_hw6.py` (for your implementation) or `test_hw6.py` (for test code) - **For tasks marked "PDF"**: you should add notes to a document that you will submit as "ans_hw6.pdf" - The stencil provides some helpers you can use **for testing purposes only**. That is, you can use them to help you write test code (i.e., `test_hw6.py`), but not in your implementation (`imp_hw6.py`). :::    # Support Code The stencil code has the following files ***which you should not modify***: - `test_helpers.py`, which defines the functions `arr_to_listnode`, `listnode_to_arr`, and `arr_to_bst`. - `classes.py`, which defines the classes `ListNode` and `TreeNode` :::danger The 3 functions in `test_helpers.py` are to be used **only for testing**. ::: The two classes in `classes.py` resemble a Singly Linked List (`ListNode`) and a Binary Search Tree (`TreeNode`). These custom implementations allow you to modify the class' instances' internal fields as you need using dot notation (e.g. `node.val = ...`). The `classes.py` file will come in useful on questions 3 (List Weaver) and 4 (Most Common Grades). # Part 1: Equal under Encoding *The Problem*: Given two strings $s1$ and $s2$ of *equal length*, determine whether they are equal under a simple character-based encoding that replaces each character in $s1$ with another character to turn it into $s2$. Each appearance of a character in $s1$ must be replaced with the same character. So, if the letter "d" appears twice in $s1$, then both must map to the *same* character in $s2$. No two characters in $s1$ can be replaced with the same character in $s2$. So, if the letters "a" and "b" both appear in $s1$, then "a" and "b" cannot map to the same character in $s2$. A character *is* allowed to be replaced with itself. :::success <details><summary>Examples</summary> <section> Example 1: Input: s1 = "dad", s2 = "bob" Output: true </section> <section> Example 2: Input: s1 = "truth", s2 = "truce" Output: false (because t in "truth" aligns with both t and c in "truce") </section> <section> Example 3: Input: s1 = "cs200", s2 = "xy900" Output: true </section> <section> Example 4: Input: s1 = "", s2 = "" Output: true </section> </details> ::: <section> ### Task 1-A (Code) Develop test cases for this question (including for edge cases). Above each test, write a 1 sentence comment articulating its unique purpose. Because the problem statement asserts that $s1$ and $s2$ are of equal length, you do not have to test for this. You may assume the two parameters are always of equal length. </section> This problem, like all of the others in this assignment, has many solutions. All of these solutions may present certain advantages and disadvantages. Consider one solution to this question: given $s1$, we generate a list of *all* potential equal encodings, with any character combination. We then loop through this list of all potential encodings and see if any of those combinations equal $s2$. <section> ### Task 1-B (PDF) What are some potential shortcomings of the above approach? As we add more characters to $s1$ and $s2$, what issue might we face? </section> Evidently, the above solution is less than ideal. There is certainly room to reduce both the *time* and *auxiliary space* complexities of the solution. One major issue with this solution is that we generate *all potential combinations* of strings and then check validity, instead of using data to remember mappings between characters that have already come up between the strings. <section> ### Task 1-C (PDF) What data structure(s) might be useful to solve this problem more efficiently? Something useful to consider - what are factors we need to keep track of to solve this problem? For each data structure, explain using **at most** 3 sentences. </section> <section> ### Task 1-D (Code) Produce a working implementation for this question under the method `equal_encoding` that satisfies **both** $O(n)$ Time Complexity and $O(n)$ Auxiliary Space Complexity, where $n$ is the length of string $s1$. Please ensure that your solution satisfies all of your test cases from Task 1-A. You should also add any additional tests that you feel are missing. </section> :::warning **Note**: If you have a solution that produces the correct answers, but does not meet both of the above efficiency requirements, *you will still receive partial credit*. ::: # Part 2: Find Sum Pair **Problem**: Given a sequence of numbers and a target number, return the indices (positions in the input list) of the two numbers that add to the target number (in the form of a set). You may assume that there is exactly one pair of indices meeting this criterion. :::info <details><summary>Examples</summary> <section> Example 1: Input: nums = [2,7,11,15], target = 9 Output: {0,1} </section> <section> Example 2: Input: nums = [3,2,4], target = 6 Output: {1,2} </section> <section> Example 3: Input: nums = [3,3], target = 6 Output: {0,1} </section> </details> ::: <section> ### Task 2-A (Code) Develop test cases for this question (including for edge cases). Above each test, write a 1 sentence comment articulating its unique purpose. You may assume that any tested target has a viable pair, and thus you do not have to test cases where this does not apply (e.g. `len(nums)` $\le$ 1 ). </section> Often, these types of questions have two types of solutions: *naive* solutions and *efficient* solutions. We consider *naive* solutions to be those that 'brute force' the answer (perhaps through an excessive amount of iterations), rather than taking advantage of a data structure to speed up the process. <section> ### Task 2-B (PDF) Upon first glance, what is the naive solution to this problem? What is its time complexity? </section> You have a goal in mind: 'find the 2 indices whose values sum to target'. If we don't want to traverse the input list as many times, what information might be useful to store across iterations? To figure this out, it helps to explicitly note what information you've gained as you process each number. <section> ### Task 2-C (PDF): Consider the list `[9, 4, 6, 8, 5]` and a desire to find a pair that sums to `11` (which would be indices `{2, 4}`). Fill in the following blanks: - After reading `9` in index 0, I could finish if I had ______________ - After reading `4` in index 1, I could finish if I had ______________ - ... Look at the insight you have accumulated in the blanks. Can you capture that in a useful data structure that would save you from having to look at each list element a second time to find the matching index? What data structure do you propose? How would you use it? Explain using **at most** 3 sentences or by providing a plan. </section> <section> ### Task 2-D (Code) Produce a working implementation for this question under the method `sum_pair` that satisfies **both** $O(n)$ Time Complexity and $O(n)$ Auxiliary Space Complexity, where $n$ is the length of the input list. Your method should take in a list of integers and a target (also an integer), and return a set of the two indices whose values sum to the target. Please ensure that your solution satisfies all of your test cases from Task 2-A. You should also add any additional tests that you feel are missing. </section> :::warning **Note**: If you have a solution that produces the correct answers, but does not meet both of the above efficiency requirements, *you will still receive partial credit*. ::: <section> ### Task 2-E (PDF) What was the auxiliary space complexity of the naive solution? Explain the time and space complexity trade-offs made between the 'naive' (2-B) and 'efficient' (2-D) solutions in **at least** 3 sentences. </section> # Part 3: List Weaver :::warning :warning: **Important note**: For this problem in particular, we **highly** recommend consulting the [Data Structure Reference](#Data-Structure-Reference) for a list of data structures we've seen in the course, and info on how to set them up. Also remember that, for some data structures, you might need to import some Python modules to get them to work (the Data Structure reference will guide you where this is necessary). There are existing functions in Python libraries that essentially already accomplish what we are asking you to do in this problem (for example, `heapq`'s [`merge` function](https://docs.python.org/3/library/heapq.html#heapq.merge)); **you may NOT use these functions**. You're still welcome to import data structure packages -- you just can't call functions that already accomplish this task. ::: **Problem**: Given a list of sorted Singly Linked Lists, weave them together into a single sorted Singly Linked List. You must retain duplicates (in other words, the length of the returned list should equal the sum of the lengths of the inputted lists).  :::success <details><summary>Examples</summary> Note: The inner lists in each of these examples' inputs are each a ListNode. <section> Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] </section> <section> Example 2: Input: lists = [[-1,4],[2,5],[-3,3,3],[-1]] Output: [-3,-1,-1,2,3,3,4,5] </section> <section> Example 3: Input: lists = [] Output: [] (None) </section> <section> Example 4: Input: lists = [[]] Output: [] (None) </section> </details> ::: <section> ### Task 3-A (Code) Develop test cases for this question (including for edge cases). Above each test, write a 1 sentence comment articulating its unique purpose. For convenience in testing, you may convert `list[int]` to a `ListNode` (Singly Linked List) of the same structure using the `arr_to_listnode` method, or a `ListNode` to a `list[int]` using `listnode_to_arr`. </section> Before attempting this problem, recall a simpler problem: how do we merge 2 Sorted Singly Linked Lists? A plan to accomplish this task might look something like the following: ``` create a list for the sorted outputs loop until both lists empty: if first item of list 1 <= first item of list 2: remove item 1 from list 1 and add it to the end of the output list if first item of list 2 < first item of list 1: remove item 1 from list 2 and add it to the end of the output list return output list as the merge of the two input lists ``` <section> ### Task 3-B (PDF) Recall that our task is to merge $k$ sorted linked lists, not just 2. How might you *change* (i.e. generalize) the above plan to accomplish this task instead? Submit the revised plan in your PDF! </section> <section> ### Task 3-C (PDF) When traversing the list elements, we want to minimize the number of times that we "touch" each element before it ends up in the output list. Think about how many touches would arise in your plan from 3-B. Give a concrete example in which some element is touched many times before going into the output. </section>  </section> Clearly, we are trying to solve the issue of repeated touches. Often, we can take advantage of the structure that our data is presented in to solve this issue. <section> ### Task 3-D (PDF) One way to minimize touches of data is to articulate what we have learned in each phase of the computation and to store that knowledge in a data structure. Consider the following example, and what we might learn if we first took the minimum of all first elements: ```=python Input: lists = [[9,10], [3,4,5,5], [5,6,7], [2,8], [1,3]] ``` In determining the minimum of 9, 3, 5, 2,and 1 (the first elements of all the lists), what will we have learned, both by direct comparison and by transitivity? - 3 is smaller than 9 - 3 is smaller than 5 - 2 is smaller than 3 (and also 5 and 9 by transitivity) - 1 is smaller than 2 (and also 2, 3, 5, and 9 by transitivity) - 1 is the smallest of the first elements - each of 9, 3, 5, 2,and 1 must appear in the output Which of these pieces of information have we *stored* or remembered after this iteration through the loop? We've stored that 1 is the smallest (by putting it in the output), and used that 1 is smaller than 2. But the information about the relationships between 2, 3, 5, and 9 have all been lost. Which means that we'll compute them again. Hence, we need a data structure that (i) can store all of these pieces of information about relationships between the numbers and (ii) helps us sort the numbers efficiently. What data structure might help?  Explain using **at least** 3 sentences. </section> --- <section> ### Task 3-E (PDF) Before creating an implementation, write out a plan for your approach. While this may not necessarily be correct on your first attempt, this should make the implementation step easier. For information on how to plan, see [this guide](https://docs.google.com/document/d/1673PEcn_6ikHpm96T0JR07nDwnOjVtvwEmaytKaZWXw/edit#heading=h.7nm12mhcv7b5). In addition, before you start your implementation, manually run two of your test cases (from Task 3-A) through your plan, and verify that it produces the correct output. You should show what happens in each step. </section> <section> ### Task 3-F (Code) Produce a working implementation for this question under the method `merge_k` that satisfies **both** $O(n \cdot log(k))$ Time Complexity and at most $O(k)$ Auxiliary Space Complexity, where $k$ is the number of input Linked Lists (i.e. the length of the outer list), and $n$ is the total number of nodes across all lists. This method will take a *list* of sorted *Singly Linked Lists*, and return one sorted Singly Linked List. You do not have to revise your plan from Step E, even if it now differs from your implementation. Please ensure that your solution satisfies all of your test cases from Task 3-A. You should also add any additional tests that you feel are missing. </section> :::warning **Note**: If you have a solution that produces the correct answers, but does not meet both of the above efficiency requirements, *you will still receive partial credit*. ::: <section> ### Task 3-G (PDF) What is the time complexity of your solution, and why? In other words, how many times does your solution "touch" each Node? What is the auxiliary space complexity of your solution, and why? Please ensure that you answer this question in Big-O notation. </section> # Part 4: Most Common Grades **Problem**: A very large course wants to do some analysis on the frequency of certain grades on the final exam. Course faculty have chosen to store students' grades in a binary search tree (BST). **Since multiple students may have same grade, this version of a BST may contain nodes with duplicate values (in either subtree).** Your task is to help them determine which overall grades occur the most often, which is called the *mode*. There may be multiple distinct grades that appear the most often (i.e. a tie). Your answer should be a set that includes all such grades. **This part is divided into two components** to help you think about the solution: **Part 4.1** examines how to compute the *mode* on a linked list, and then **Part 4.2** extends this to the BST version. ## Part 4.1: Linked list version Before we take on this larger problem, let's work through a simpler problem that should inspire part of the solution. <section> ### Task 4-A (PDF) Let's say that we simply have a **sorted** Singly Linked list, called `nums_list`. How might one compute the mode (or modes, if there are ties) of this list? Develop a plan for a program `ll_modes` that computes the set of modes for a singly-linked list named `nums_list`. An intuitive approach would be to use a dictionary to store the count of each unique item as you iterate through the list. However, we **do not want you to use this approach** (this will help you with 4.2). Can you think of a solution that uses no data structures aside from the input singly linked list and the hashset that saves return result? </section> <section> ### Task 4-B (Code) **Implement** `ll_modes`. Create a couple basic tests, and ensure that your new method works as intended. Above each test, write a 1 sentence comment articulating its unique purpose. For convenience in testing, you may convert `list[int]` to a `ListNode` (Singly Linked List) of the same structure using the `arr_to_listnode` method. </section> :::danger Before moving on, you should have a **working** `ll_modes` implementation. ::: ## Part 4.2: BST version Let's now abstract back to the problem of finding the modes of a *binary search tree (BST)*. One idea is to use dictionaries. :::success Consider the following dictionary-based solution to this problem. <details><summary>Expand Me!</summary> ![](https://docs.cs200.io/uploads/b22ed836-cdf1-48c8-8b2d-15b739f6b773.png) ![](https://docs.cs200.io/uploads/ff879f5f-f157-44df-9466-39931a8fdc9b.png) ![](https://docs.cs200.io/uploads/611d789e-10dc-4980-91db-c9e330d6da9a.png) </details> ::: The above implementation certainly works on a BST. However, it **also** works on **any** binary tree. This seems like a missed opportunity, since the structure of a BST provides information that we don't get with a general binary tree. <section> ### Task 4-C (PDF) What structural property of a BST can we take *advantage of* to find a more efficient solution to this problem? :::success **Hint**: What is the relationship between a BST and a *sorted* linked list? How might you apply your *sorted* Linked List mode algorithm to a BST? ::: </section> :::danger Before moving on, you should have a conceptual understanding of how to answer the question in the hint above. In other words, you should have an understanding of how you intend to **traverse** the binary search tree to calculate its mode(s). ::: Let's try to create our more-efficient implementation for finding the mode of a BST. :::success <details><summary>Examples</summary> <section> Example 1: Input: root = [1,None,2,None,None,2] Output: {2} ![](https://docs.cs200.io/uploads/501a161a-fb7b-44f7-8000-582a55de49f8.png =100x140) </section> <section> Example 2: Input: root = [5,4,8,3,4,7,9] Output: {4} ![](https://docs.cs200.io/uploads/778102e4-8bdc-4f40-96f6-4a473c53e245.png =200x130) </section> <section> Example 3: Input: root = [1,0,1,0,0,1,1,0] Output: {0,1} ![](https://docs.cs200.io/uploads/28857e11-3d3e-427c-979d-deab8851a380.png =200x130) </section> <section> Example 3: Input: root = [] Output: {} </section> </details> ::: <section> ### Task 4-D (Code) Develop both *traditional* and *edge* test cases for this question. Above each test, write a 1 sentence comment articulating its unique purpose. For convenience in testing, you may convert `list[int]` to a `TreeNode` (BST) of the same structure using the `arr_to_bst` method. </section> <section> ### Task 4-E (Code) Produce a working implementation for this question under the method `bst_modes` that satisfies **both** $O(n)$ Time Complexity and $O(n)$ Auxiliary Space Complexity, where $n$ is the total number of nodes in the BST. This method will take in a `TreeNode` (BST) and output the set of all modes. :::danger Because we have already shown you a dictionary-based solution, your own solution to this problem **cannot** use a dictionary. ::: Please ensure that your solution satisfies all of your test cases from Task 4-D. You should also add any additional tests that you feel are missing. </section> :::warning **Note**: If you have a solution that produces the correct answers, but does not meet both of the above efficiency requirements, *you will still receive partial credit*. ::: :::danger Before moving on, you should have a **working** `bst_modes` implementation. ::: --- You might have noticed that both your solution and the dictionary solution have $O(n)$ Time Complexities. That's odd though -- surely leveraging the structure within a BST would make *some* difference. For example, perhaps the BST-aware algorithm computes fewer iterations by raw count---or avoids the worst-case time inherent by $O$---than the dictionary-based algorithm. <section> ### Task 4-F (PDF) Do we expect an algorithm that only works on the BST version (by taking advantage of the BST's structure) to have a noticeably better run time in practice (e.g. in industry) than an algorithm that also works on plain binary trees? Under what conditions? Explain your answer in **at least** 4 sentences. </section> # **Handing In** You should submit the following files to Gradescope using the **Homework 6: Implementation** assignment: - `imp_hw6.py` - `test_hw6.py` - `test_helpers.py` (**unmodified**) - `classes.py` (**unmodified**) - `ans_hw6.pdf` There is no separate testing submission for this assignment. We will grade your tests manually, based on the descriptions of what we have asked you to test throughout this assignment. Once you have handed in your homework, you should receive an email, more or less immediately, confirming that fact. If you don’t receive this email, try handing in again, or ask the TAs what went wrong. :::success Congratulations, you have finished your final CS200 homework! Well done! ::: # Grading 1. **Equal Under Encoding** (20%) 2. **Find Sum Pair** (10%) 3. **List Weaver** (35%) 4. **Most Common Grades** (35%) For each of the above, your *implementation* functionality (submitted in `imp_hw6.py`) will be autograded on Gradescope. Both the thoroughness of your tests (submitted in `test_hw6.py`) and your method efficiencies (submitted in `imp_hw6.py`) will be graded manually. As for **(PDF)** questions: they should all be submitted in ***1 PDF*** named `ans_hw6.pdf`. Please label your answers to each task clearly and in order. For each individual question, the grading split within that question is as follows... 1. **Implementation Functionality** (40%) -- Autograded 2. **Runtime Adherence** (25%) -- Manual 3. **Testing** (15%) -- Manual 4. **Writing Questions** (20%) -- Manual # Data Structure Reference Unlike Java, where most data structures are clearly named (i.e. LinkedList, ArrayList, etc.), Python is more loose with its creation and representation of data structures. This guide will demonstrate *how* to create each type of data structure in Python, if you need it. The data structures we have seen so far include: - Lists (`ArrayList` in Java) - Linked Lists (`LinkedList` in Java) - Dictionaries (`HashMap` in Java) - Sets (`HashSet` in Java) - Graphs - Binary Tree - Priority Queues and Heaps ## Lists Creating a dynamic list (i.e. one that can change size) in Python can be done in two simple ways: 1. `my_list = []` 2. `my_list = list()` Both of these are equivalent ways to instantiate a list under the variable name `my_list` in Python. ## Linked Lists Python *does not* have a built-in version of a LinkedList like Java. However, we can create versions of this data structure using Python classes. In `classes.py`, we provide a custom implementation of a LinkedList called `ListNode`, which is for all intents and purpose is identical to a Singly Linked Lists, which is defined like this: ```python @dataclass class ListNode: def __init__(self, val: int=0, next: "ListNode"=None): self.val = val # The node's value (an integer) self.next = next # The next node (or None) ``` Our `ListNode` implementation is actually implemented with Python's `dataclass`, which is a way to quickly make data structures. You can interact with `ListNode`'s just like any other Python object--if you are curious on the internal workings of dataclasses, check out [their documentation](https://docs.python.org/3/library/dataclasses.html). ## Dictionaries Creating a dictionary in Python can be done in two ways: 1. `my_dict = {}` 2. `my_dict = dict()` ## Sets You can initialize a set in Python via the following line: `my_set = set()` ## Graphs Like Java, Python *does not* have a built-in version of a Graph. However, we can create versions of this data structure using Python classes. For example, we could instantiate a series of interconnected `Node`s using the class below, which would represent a unidirectional graph (similar to what you saw in GraphQuest). ```python class Node: def __init__(self, value): self.value = value self.neighbors = [] def add_neighbor(self, neighbor): self.neighbors.append(neighbor) def add_neighbors(self, list_of_neighbors): for neighbor in list_of_neighbors: self.add_neighbor(neighbor) ``` ## Binary Trees Python *does not* have a built-in version of a binary tree like Java. However, we can create versions of this data structure using Python classes. In `classes.py`, we provide a custom implementation of a binary tree called `TreeNode`, which is identical to a binary tree and is defined like this: ```python @dataclass class TreeNode: def __init__(self, val: int=0, left: "TreeNode"=None, right: "TreeNode"=None): self.val = val # The node's value (an integer) self.left = left # The left node (or None) self.right = right # The left node (or None) ``` Our `TreeNode` implementation is actually implemented with Python's `dataclass`, which is a way to quickly make data structures. You can interact with `TreeNode`'s just like any other Python object--if you are curious on the internal workings of dataclasses, check out [their documentation](https://docs.python.org/3/library/dataclasses.html). ## Priority Queues and Heaps While Python does not provide a built-in implementation for a priority queue or heap, they are provided in Python's stardard library--**to use them, you must import these modules into your Python file**. For example, if you need to use a Priority Queue or Heap, then type either of the following at the top of your `.py` file: 1. `from queue import PriorityQueue` 2. `import heapq` **You are allowed to import either of these packages for Homework 6.** To work with either of these packages, both of which have the same functionality invoked in different forms, you can read through their documentations: - For the `PriorityQueue` documentation, see [here](https://docs.python.org/3/library/queue.html). - For the `heapq` documentation, see [here](https://docs.python.org/3/library/heapq.html). *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our_ [_anonymous feedback form_](https://forms.gle/Myj4XSPx8cBJLxGt5)_!_