(Suggested book reading: Programming Abstractions in C++, Chapter 16, section 16.1)
Today we'll learn about a way of organizing data in memory called a binary tree. A binary tree shares some aspects of the linked list that you have just studied. Just like linked list has two parts that work together: ListNode (holds a piece of data and a "next" pointer) and LinkedList (holds a pointer to only the first node of the list, from which we can traverse and access the whole list), binary trees have a TreeNode and BinaryTree that work together.
Trees are useful throughout computer science. For example, the folders (directories) on a computer form a tree structure--each folder can contain more folders. Note that folders form a tree structure but not necessarily a binary tree structure, because a folder may have more than two sub-folders contained within it. Other tree structures include a family genealogy, a corporate organizational chart, (in AI) a decision tree, (in compilers) a parse tree ("a = (b+c) * d;"), or cell phone word auto-completion.
Binary tree terminology:
You are expected to follow the Stanford Honor Code.
If this is an assignment that allows pairs, the same rules apply to each team. For example, do not look at assignment solutions that do not belong to your team, and do not give your solution to anyone outside of your team.
Remember that we run similarity-detection software over all solutions, including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you. You can go to the LaIR, or the course message forum, or email your section leader, or visit the instructor / head TA during office hours. You can do it!