Thumbtack
Tree and Graph Data Structures
4 hours, 13 minutes
CC
Course Description
Learn the implementation details of tree and graph data structures, interview questions involving them, and the algorithms to solve them. This course builds on Bianca’s Practical Algorithms and Data Structures for Interviews courses. Unlike arrays, trees and graphs are non-linear. This allows for modeling things such as recommendation algorithms and social networks.
This course and others like it are available as part of our Frontend Masters video subscription.
Preview
CloseLearn Straight from the Experts Who Shape the Modern Web
Your Path to Senior Developer and Beyond
- 200+ In-depth courses
- 18 Learning Paths
- Industry Leading Experts
- Live Interactive Workshops
Table of Contents
Introduction
Section Duration: 41 minutes
Bianca gives an overview of what will be covered in the course. Then, students are asked to give tips for effective learning.
Bianca reviews the array and linked list linear data structures, and describes the time complexity of common array and linked list operations.
Bianca reviews the stack and queue linear data structures and describes the time complexity of common stack and queue operations.
Bianca distinguishes between linear and non-linear data structures and highlights strengths of trees and graphs, which are non-linear.
Bianca models a chatbot to solve the problem of deciding on breakfast each morning and plans out its desired behavior.
Bianca introduces trees by coding a basic tree in JavaScript, diagramming its various parts, and giving real-world examples.
Bianca challenges students to draw out a model of the chatbot using linear data structures.
Bianca fields student ideas about how to implement a chatbot using linear data structures.
Trees
Section Duration: 29 minutes
Bianca presents an example of a tree data structure representing a family and analyzes its structure.
Bianca instructs students to code the insert method for trees. Optionally, students are also challenged to write a remove method.
Bianca gives the solution to the exercise and explains what is occurring while using insert to create three connected trees.
Bianca explains various ways the remove method can be coded and the implications of each in terms of time complexity and data loss.
Bianca discusses how the recommendations should be structured within the chatbot tree.
Bianca demonstrates one way to code the structure of a basic tree for the inner structure of the chatbot.
Tree Traversal
Section Duration: 1 hour, 7 minutes
Bianca introduces binary tree traversal by explaining what order nodes will be visited using the preorder traversal technique.
Bianca uses loops to live code a traversal function for binary trees that prints the value of a root node and its leaf nodes.
Bianca uses recursion to live code a preorder traversal function for binary trees that prints the value of every node in the tree.
Bianca instructs students to write a traverse method for binary trees.
Bianca live codes the solution to the exercise for the traverse method for binary trees.
Bianca live codes the solution to the exercise for the contains method for binary trees.
Bianca walks through each recursive step in the execution of the contains solution for binary trees and discusses usage of recursion in interviews.
Bianca live codes a method to count the number of recommendation nodes within the chatbot binary tree by walking through iterations of the code.
Bianca outlines the time complexity of the four methods for trees that were covered in previous lessons.
Bianca describes preorder, inorder, and postorder tree traversal and explains what it means to use each one.
Graphs
Section Duration: 37 minutes
Bianca introduces graphs by giving examples of what they can represent and displaying a visualization of breakfast recommendations as a graph.
Bianca analyzes the adjacency matrix format of representing node relationships in a graph, using binary values in the array.
Bianca analyzes the adjacency list format of representing node relationships in a graph using node values in the array.
Bianca compares the adjacency matrix and adjacency list graph representations in terms of time complexity.
Bianca instructs students to write methods for operating on graphs, using an adjacency list for the data structure.
Bianca live codes the graph constructor, add node, add edge, and remove node methods for graphs using an adjacency list for edges.
Graph Search
Section Duration: 1 hour, 15 minutes
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.
Bianca steps through the process of executing depth first search to demonstrate the order nodes are visited.
Bianca instructs students to code a method to perform depth first search on a graph.
Bianca walks through a method that performs depth first search on a graph in JavaScript and then reviews the solution's time complexity.
Bianca describes the process of performing a breadth first search on a graph and gives tips for understanding the order nodes will be visited.
Bianca instructs students to code a method to perform breadth first search on a graph and answers questions about its implementation.
Bianca walks through a method that performs breadth first search on a graph and then reviews the solution's time complexity.
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.
Bianca introduces directed graphs by describing various properties that differ based on the type of graph being used.
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.
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.
Bianca leads an activity to take an empty binary search tree and fill in its node values, given an array of numerical node values.
Bianca analyzes each step in the process of inserting a node into a preexisting binary search tree.
Bianca instructs students to write the search method for binary search trees, and completes a brief walkthrough of how the method should work.
Bianca walks through the solution for searching binary trees, and additionally walks through the necessary constructor and insert methods.
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.
Wrapping Up
Section Duration: 1 minute
Bianca wraps up the course by mentioning further resources for students to keep learning.
Learn Straight from the Experts Who Shape the Modern Web
- In-depth Courses
- Industry Leading Experts
- Learning Paths
- Live Interactive Workshops