# Tree and Graph Data Structures

## Bianca Gandolfo

Thumbtack
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
Close
Get \$100 Off
Get \$100 Off!

### Course Details

Published: May 20, 2019

## Learn Straight from the Experts Who Shape the Modern Web

Your Path to Senior Developer and Beyond
• 200+ In-depth courses
• 18 Learning Paths
• Live Interactive Workshops
Get Unlimited Access Now

### Introduction

Section Duration: 41 minutes
• ### Course Overview

00:00:00 - 00:07:14 View Transcript
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

00:07:15 - 00:13:01 View Transcript
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

00:13:02 - 00:23:18 View Transcript
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

00:23:19 - 00:26:26 View Transcript
Bianca distinguishes between linear and non-linear data structures and highlights strengths of trees and graphs, which are non-linear.
• ### Modeling a Chatbot

00:26:27 - 00:30:43 View Transcript
Bianca models a chatbot to solve the problem of deciding on breakfast each morning and plans out its desired behavior.
• ### Introduction to Trees

00:30:44 - 00:35:26 View Transcript
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

00:35:27 - 00:36:28 View Transcript
Bianca challenges students to draw out a model of the chatbot using linear data structures.
• ### Exploring Data Modeling

00:36:29 - 00:41:24 View Transcript
Bianca fields student ideas about how to implement a chatbot using linear data structures.

### Trees

Section Duration: 29 minutes
• ### Family Trees

00:41:25 - 00:42:44 View Transcript
Bianca presents an example of a tree data structure representing a family and analyzes its structure.
• ### Tree insert & remove Exercise

00:42:45 - 00:43:22 View Transcript
Bianca instructs students to code the insert method for trees. Optionally, students are also challenged to write a remove method.
• ### Tree insert Solution

00:43:23 - 00:52:30 View Transcript
Bianca gives the solution to the exercise and explains what is occurring while using insert to create three connected trees.
• ### Tree remove Solution

00:52:31 - 00:59:19 View Transcript
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

00:59:20 - 01:01:57 View Transcript
Bianca discusses how the recommendations should be structured within the chatbot tree.
• ### Coding a Tree

01:01:58 - 01:10:37 View Transcript
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
• ### Tree Traversal

01:10:38 - 01:11:48 View Transcript
Bianca introduces binary tree traversal by explaining what order nodes will be visited using the preorder traversal technique.
• ### Traversing One Tree

01:11:49 - 01:20:54 View Transcript
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

01:20:55 - 01:33:42 View Transcript
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

01:33:43 - 01:36:16 View Transcript
Bianca instructs students to write a traverse method for binary trees.
• ### Binary Tree traverse Solution

01:36:17 - 01:40:30 View Transcript
Bianca live codes the solution to the exercise for the traverse method for binary trees.
• ### Binary Tree contains Solution

01:40:31 - 01:53:10 View Transcript
Bianca live codes the solution to the exercise for the contains method for binary trees.
• ### Binary Tree contains Walkthrough

01:53:11 - 02:00:41 View Transcript
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

02:00:42 - 02:14:29 View Transcript
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

02:14:30 - 02:16:35 View Transcript
Bianca outlines the time complexity of the four methods for trees that were covered in previous lessons.
• ### Tree Traversal Order

02:16:36 - 02:17:51 View Transcript
Bianca describes preorder, inorder, and postorder tree traversal and explains what it means to use each one.

### Graphs

Section Duration: 37 minutes
• ### Drawing a Graph

02:17:52 - 02:22:35 View Transcript
Bianca introduces graphs by giving examples of what they can represent and displaying a visualization of breakfast recommendations as a graph.

02:22:36 - 02:30:24 View Transcript
Bianca analyzes the adjacency matrix format of representing node relationships in a graph, using binary values in the array.

02:30:25 - 02:36:40 View Transcript
Bianca analyzes the adjacency list format of representing node relationships in a graph using node values in the array.
• ### Matrix vs List Comparison

02:36:41 - 02:39:37 View Transcript
Bianca compares the adjacency matrix and adjacency list graph representations in terms of time complexity.
• ### Graph Exercise

02:39:38 - 02:41:42 View Transcript
Bianca instructs students to write methods for operating on graphs, using an adjacency list for the data structure.
• ### Graph Solution

02:41:43 - 02:55:49 View Transcript
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
• ### Search & Personal Recommendations

02:55:50 - 02:59:46 View Transcript
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

02:59:47 - 03:04:26 View Transcript
Bianca steps through the process of executing depth first search to demonstrate the order nodes are visited.
• ### Depth First Search Exercise

03:04:27 - 03:06:05 View Transcript
Bianca instructs students to code a method to perform depth first search on a graph.
• ### Depth First Search Solution

03:06:06 - 03:13:59 View Transcript
Bianca walks through a method that performs depth first search on a graph in JavaScript and then reviews the solution's time complexity.

03:14:00 - 03:17:58 View Transcript
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

03:17:59 - 03:19:18 View Transcript
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

03:19:19 - 03:24:54 View Transcript
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

03:24:55 - 03:31:17 View Transcript
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

03:31:18 - 03:39:23 View Transcript
Bianca introduces directed graphs by describing various properties that differ based on the type of graph being used.
• ### Binary Search

03:39:24 - 03:48:38 View Transcript
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

03:48:39 - 03:51:30 View Transcript
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

03:51:31 - 03:53:08 View Transcript
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

03:53:09 - 03:55:22 View Transcript
Bianca analyzes each step in the process of inserting a node into a preexisting binary search tree.
• ### Binary Search Exercise

03:55:23 - 03:57:19 View Transcript
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

03:57:20 - 04:05:46 View Transcript
Bianca walks through the solution for searching binary trees, and additionally walks through the necessary constructor and insert methods.
• ### Binary Search Time Complexity

04:05:47 - 04:11:59 View Transcript
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

### Learn Straight from the Experts Who Shape the Modern Web

• In-depth Courses