You should be able to:
- Define and distinguish Abstract Data Types (ADT) and Data Structures (DS)
- Describe how both a stack and a queue work (how are they different, what similarities do they have, etc)
- Implement a Linked List and Binary Search Tree (BST) class
- Explain the high-level differences between depth-first and breadth-first search
- Explain the differences between pre-order, in-order, and post-order processing
- Enqueue: Queue
- Dequeue: Queue
- Push: Stack
- Pop: Stack
- Traverses tree by level by level: Breadth First Search
- Traverses tree branch by branch: Depth First Search
- Good for copying a BST: Depth First Search (Pre-order)
- Produces a sorted list of items from a BST: In-order (left, root, right)
- Remove all tree nodes from memory: Post-order (right, left, root)
- Clone a binary search tree: Pre-order (root, left, right)
Trees!
- I like binary search tree the most because it can help break down complex comparison problems into sets of simple comparison among three values, which is an amazing idea to increase the efficiency of problem-solving process.
- Trees! I love how smoothly trees fit into recursion, it makes for really cool functionality that can be expressed super simply.
- Binary Search Tree because it's relatively easier for visualization.
Linked Lists!
- Linked list because in some cases they are more efficient than arrays for example insertion always has a constant time
- Linked lists, because of their simple design. And liked binary search trees because of the work it provided to brain for implementing various methods!
Other!
- (Even this is an ADT...) I loved learning about stacks. I couldn't think of a useful implementation when that was first asked in lecture, but now it make so much sense how they are the ADT behind callstack, browser history, command z, etc :)
- Queues are interesting to me because of the first-in-first-out (FIFO) idea. It seems like queues are quite useful.