Tree and Graph Data Structures
Table of Contents
Course OverviewBianca gives an overview of what will be covered in the course. Then, students are asked to give tips for effective learning.
Arrays & Linked Lists ReviewBianca reviews the array and linked list linear data structures, and describes the time complexity of common array and linked list operations.
Stacks & Queues ReviewBianca reviews the stack and queue linear data structures and describes the time complexity of common stack and queue operations.
Linear vs Non-Linear Data StructuresBianca distinguishes between linear and non-linear data structures and highlights strengths of trees and graphs, which are non-linear.
Modeling a ChatbotBianca models a chatbot to solve the problem of deciding on breakfast each morning and plans out its desired behavior.
Linear vs Non-Linear Data ModelingBianca challenges students to draw out a model of the chatbot using linear data structures.
Exploring Data ModelingBianca fields student ideas about how to implement a chatbot using linear data structures.
Family TreesBianca presents an example of a tree data structure representing a family and analyzes its structure.
Tree insert & remove ExerciseBianca instructs students to code the insert method for trees. Optionally, students are also challenged to write a remove method.
Tree insert SolutionBianca gives the solution to the exercise and explains what is occurring while using insert to create three connected trees.
Tree remove SolutionBianca explains various ways the remove method can be coded and the implications of each in terms of time complexity and data loss.
Chatbot RecommendationsBianca discusses how the recommendations should be structured within the chatbot tree.
Coding a TreeBianca demonstrates one way to code the structure of a basic tree for the inner structure of the chatbot.
Tree TraversalBianca introduces binary tree traversal by explaining what order nodes will be visited using the preorder traversal technique.
Traversing One TreeBianca uses loops to live code a traversal function for binary trees that prints the value of a root node and its leaf nodes.
Traversing Nested TreesBianca uses recursion to live code a preorder traversal function for binary trees that prints the value of every node in the tree.
Binary Tree Traversal ExerciseBianca instructs students to write a traverse method for binary trees.
Binary Tree traverse SolutionBianca live codes the solution to the exercise for the traverse method for binary trees.
Binary Tree contains SolutionBianca live codes the solution to the exercise for the contains method for binary trees.
Binary Tree contains WalkthroughBianca walks through each recursive step in the execution of the contains solution for binary trees and discusses usage of recursion in interviews.
Count RecommendationsBianca live codes a method to count the number of recommendation nodes within the chatbot binary tree by walking through iterations of the code.
Tree Methods Time ComplexityBianca outlines the time complexity of the four methods for trees that were covered in previous lessons.
Tree Traversal OrderBianca describes preorder, inorder, and postorder tree traversal and explains what it means to use each one.
Drawing a GraphBianca introduces graphs by giving examples of what they can represent and displaying a visualization of breakfast recommendations as a graph.
Adjacency MatrixBianca analyzes the adjacency matrix format of representing node relationships in a graph, using binary values in the array.
Adjacency ListBianca analyzes the adjacency list format of representing node relationships in a graph using node values in the array.
Matrix vs List ComparisonBianca compares the adjacency matrix and adjacency list graph representations in terms of time complexity.
Graph ExerciseBianca instructs students to write methods for operating on graphs, using an adjacency list for the data structure.
Graph SolutionBianca live codes the graph constructor, add node, add edge, and remove node methods for graphs using an adjacency list for edges.
Search & Personal RecommendationsBianca introduces two ways to search a graph, by exploring depth first and by exploring breadth first, and explains how this will allow for personal recommendations.
Depth First SearchBianca steps through the process of executing depth first search to demonstrate the order nodes are visited.
Depth First Search ExerciseBianca instructs students to code a method to perform depth first search on a graph.
Breadth First SearchBianca describes the process of performing a breadth first search on a graph and gives tips for understanding the order nodes will be visited.
Breadth First Search ExerciseBianca instructs students to code a method to perform breadth first search on a graph and answers questions about its implementation.
Breadth First Search SolutionBianca walks through a method that performs breadth first search on a graph and then reviews the solution's time complexity.
Depth-First & Breadth-First Search UsageBianca leads a discussion about which type of search to use in the implementation of the breakfast recommendation tree, along with common uses for the two search methods.
Directed GraphsBianca introduces directed graphs by describing various properties that differ based on the type of graph being used.
Binary SearchBianca reviews linear search method and time complexity on graphs, and then introduces binary search. What to do when given a search problem in interviews is also discussed.
Binary Search TreesBianca explains what a binary search tree is, gives benefits of using binary search trees, and displays a basic representation of how it could be implemented in code.
Fill the Tree ActivityBianca leads an activity to take an empty binary search tree and fill in its node values, given an array of numerical node values.
insert NodeBianca analyzes each step in the process of inserting a node into a preexisting binary search tree.
Binary Search ExerciseBianca instructs students to write the search method for binary search trees, and completes a brief walkthrough of how the method should work.
Binary Search SolutionBianca walks through the solution for searching binary trees, and additionally walks through the necessary constructor and insert methods.
Binary Search Time ComplexityBianca analyzes the time complexity of using the search method on binary trees, and explains how it is related to the tree's height. The distinction between balanced and unbalanced trees is also discussed.