Tree and Graph Data Structures
Learning Paths:
Topics:
Table of Contents
Introduction
Course Overview
Bianca gives an overview of what will be covered in the course. Then, students are asked to give tips for effective learning.
Arrays & Linked Lists Review
Bianca reviews the array and linked list linear data structures, and describes the time complexity of common array and linked list operations.
Stacks & Queues Review
Bianca reviews the stack and queue linear data structures and describes the time complexity of common stack and queue operations.
Linear vs Non-Linear Data Structures
Bianca distinguishes between linear and non-linear data structures and highlights strengths of trees and graphs, which are non-linear.
Modeling a Chatbot
Bianca models a chatbot to solve the problem of deciding on breakfast each morning and plans out its desired behavior.
Introduction to Trees
Bianca introduces trees by coding a basic tree in JavaScript, diagramming its various parts, and giving real-world examples.
Linear vs Non-Linear Data Modeling
Bianca challenges students to draw out a model of the chatbot using linear data structures.
Exploring Data Modeling
Bianca fields student ideas about how to implement a chatbot using linear data structures.
Trees
Family Trees
Bianca presents an example of a tree data structure representing a family and analyzes its structure.
Tree insert & remove Exercise
Bianca instructs students to code the insert method for trees. Optionally, students are also challenged to write a remove method.
Tree insert Solution
Bianca gives the solution to the exercise and explains what is occurring while using insert to create three connected trees.
Tree remove Solution
Bianca explains various ways the remove method can be coded and the implications of each in terms of time complexity and data loss.
Chatbot Recommendations
Bianca discusses how the recommendations should be structured within the chatbot tree.
Coding a Tree
Bianca demonstrates one way to code the structure of a basic tree for the inner structure of the chatbot.
Tree Traversal
Tree Traversal
Bianca introduces binary tree traversal by explaining what order nodes will be visited using the preorder traversal technique.
Traversing One Tree
Bianca 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 Trees
Bianca 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 Exercise
Bianca instructs students to write a traverse method for binary trees.
Binary Tree traverse Solution
Bianca live codes the solution to the exercise for the traverse method for binary trees.
Binary Tree contains Solution
Bianca live codes the solution to the exercise for the contains method for binary trees.
Binary Tree contains Walkthrough
Bianca walks through each recursive step in the execution of the contains solution for binary trees and discusses usage of recursion in interviews.
Count Recommendations
Bianca 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 Complexity
Bianca outlines the time complexity of the four methods for trees that were covered in previous lessons.
Tree Traversal Order
Bianca describes preorder, inorder, and postorder tree traversal and explains what it means to use each one.
Graphs
Drawing a Graph
Bianca introduces graphs by giving examples of what they can represent and displaying a visualization of breakfast recommendations as a graph.
Adjacency Matrix
Bianca analyzes the adjacency matrix format of representing node relationships in a graph, using binary values in the array.
Adjacency List
Bianca analyzes the adjacency list format of representing node relationships in a graph using node values in the array.
Matrix vs List Comparison
Bianca compares the adjacency matrix and adjacency list graph representations in terms of time complexity.
Graph Exercise
Bianca instructs students to write methods for operating on graphs, using an adjacency list for the data structure.
Graph Solution
Bianca live codes the graph constructor, add node, add edge, and remove node methods for graphs using an adjacency list for edges.
Graph Search
Search & Personal Recommendations
Bianca 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 Search
Bianca steps through the process of executing depth first search to demonstrate the order nodes are visited.
Depth First Search Exercise
Bianca instructs students to code a method to perform depth first search on a graph.
Depth First Search Solution
Bianca walks through a method that performs depth first search on a graph in JavaScript and then reviews the solution's time complexity.
Breadth First Search
Bianca 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 Exercise
Bianca instructs students to code a method to perform breadth first search on a graph and answers questions about its implementation.
Breadth First Search Solution
Bianca 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 Usage
Bianca 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 Graphs
Bianca introduces directed graphs by describing various properties that differ based on the type of graph being used.
Binary Search
Bianca 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 Trees
Bianca 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 Activity
Bianca leads an activity to take an empty binary search tree and fill in its node values, given an array of numerical node values.
insert Node
Bianca analyzes each step in the process of inserting a node into a preexisting binary search tree.
Binary Search Exercise
Bianca instructs students to write the search method for binary search trees, and completes a brief walkthrough of how the method should work.
Binary Search Solution
Bianca walks through the solution for searching binary trees, and additionally walks through the necessary constructor and insert methods.
Binary Search Time Complexity
Bianca 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.
