# Tree and Graph Data Structures

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.