Skip to content

Week 09 - November 13

Class Description

This week we explore hierarchical data structures: linked lists, trees, binary trees, and tries. These structures are fundamental to computer science and power everything from file systems to autocomplete features to efficient searching and sorting.

Key Connection: Linked structures provide flexibility → Recursion enables elegant tree algorithms → OOP provides clean implementations → These structures form the foundation for advanced data structures.

Key Learning Objectives: - Understand linked lists and their advantages over arrays - Implement singly and doubly linked lists with insertion, deletion, and traversal - Master tree terminology: root, parent, child, leaf, height, depth - Design object-oriented tree systems with TreeNode and Tree classes - Implement binary trees and understand their properties - Traverse trees using in-order, pre-order, and post-order methods - Understand binary search trees (BST) and their O(log n) search capabilities - Explore tries (prefix trees) for efficient string storage and retrieval - Apply recursive thinking to tree operations

Before Class

Videos to Watch Before Class

CS 5002 - Module: Linked Lists, Trees, and Tries

Linked Lists: - Linked Lists

Trees: - Trees - Part 1 - Trees - Part 2

Binary Trees: - Binary Trees - Part 1 - Binary Trees - Part 2

Tree Traversal: - Tree Traversal - Part 1 - Tree Traversal - Part 2

Tries (Prefix Trees): - Tries

Binary Search Trees (BST): - Binary Search Trees - BST Interactive Visualization (interactive demo)

CS 5001 - Review: Linked Lists (if needed)

  • Recursion is essential for understanding tree operations
  • Review recursive thinking and base cases
  • Practice with simple recursive problems before class

LLM Learning Prompts

Use these prompts with ChatGPT, Claude, or other AI assistants to deepen your understanding:

Linked Lists: 

Explain linked lists in Python with a simple example. Show me how to implement 
insertion, deletion, and traversal. Compare linked lists to arrays - when would 
I use each? Include time complexity analysis.

Trees: 

Teach me about tree data structures. Start with basic terminology (root, parent, 
child, leaf, height, depth). Show me how to implement a basic tree in Python with 
examples. Explain the difference between binary trees and general trees.

Binary Trees: 

Explain binary trees with concrete examples. Show me how to implement a binary 
tree node class in Python. Walk me through creating a simple binary tree and 
explain its properties and use cases.

Tree Traversal: 

Teach me the three main tree traversal methods: in-order, pre-order, and post-order. 
For each one, explain when to use it and show me Python implementations. Use a 
concrete tree example and show the output for all three traversals.

Binary Search Trees (BST): 

Explain binary search trees and the BST property (left < parent < right). Show me 
how to implement insert, search, and delete operations in Python. Why is BST search 
O(log n) on average? When does it degrade to O(n)?

Tries (Prefix Trees): 

Explain tries (prefix trees) and their advantages for string operations. Show me 
how to implement a trie in Python for storing words. Demonstrate how tries are used 
for autocomplete functionality. Compare space and time complexity to other approaches.

General Understanding: 

I'm learning about [topic]. Can you create a small practice problem for me? After 
I attempt it, review my solution and suggest improvements.

Additional Resources

Linked Lists: - Singly vs. doubly linked lists - When to use linked lists vs. arrays - Common operations: insertion, deletion, reversal

Trees: - Tree terminology and properties - Binary tree vs. general tree - Tree traversal algorithms (in-order, pre-order, post-order)

Binary Search Trees: - BST property: left < parent < right - Search, insert, delete operations - Time complexity analysis

Tries (Prefix Trees): - Efficient string storage and retrieval - Autocomplete applications - Space vs. time trade-offs