# Data Structures and Algorithms in JavaScript

This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Table of Contents

## Object Oriented JavaScript

### Introduction

Bianca Gandolfo begins her Data Structures & Algorithms course by sharing her background and how she developed this course. She will be using a cooking metaphor throughout the course because she believes learning these concepts involves understanding the "recipes", watching them in action, and getting time to try them out yourself.### Agenda and Scope

Bianca quickly walks through the agenda and scope of this six-day course. The fundamentals introduced and practiced in the first day will be used throughout the rest of the course. This course is based on university-level computer science courses and covers the most common data structures and algorithms programmers use today.### How to Succeed

Using a "fad diet" metaphor, Bianca explains what it takes to succeed in this course. She recommends pairing up with someone or a team of people to try the exercises and discuss the solutions. Ask questions and don't be afraid of failure.### Pseudoclassical JavaScript

JavaScript is often referred to as "pseudoclassical" because it's an object-oriented language but lacks a formal way of creating class constructors. While this changes in ES6, Bianca introduces this concept of pseudoclassical JavaScript and leads a discussion about why data needs structure.### Defining a Class

Bianca presents her recipe for defining a class in JavaScript. She describes the constructor and properties as an object's "what it is" and "what it has". Methods on the object are "what it does".### Using a Class

Before moving into the first exercise, Bianca shares a few examples of how classes are used in JavaScript. She also talks about what parts of pseudoclassical JavaScript are typically required knowledge in job interviews.### Exercise: Creating a Constructor

In this exercise, you will create a unique constructor that creates a building of your choice. Your constructor will use the pseudoclassical JavaScript pattern.### Creating a Constructor Solution

Bianca walks through the solution to the Creating a Constructor exercise.

## Stacks & Queues

### Stacks

The first data structure Bianca introduces is a stack. With each data structure, she will be drawing it out, pseudocoding it, then putting it to work with an API and any applicable algorithms. The stacks API follows a last-in-first-out model where the last item added to the stack is the first item removed.### Stacks Interface

The interface for a stack contains a constructor function for handling the storage along with push(), pop(), and size() methods for manipulating the stack. After introducing the interface, Bianca share an example of the methods defined in JavaScript.### Implementing a Stack

Bianca implements each method of the Stack object. The constructor initializes the storage object. In this case, she's using a String for storing the stack data. She then implements the push() and pop() methods which add and remove items from the stack.### Queues

Queues are similar to a stack except for the order in which items are added. In the case of a queue, the first item in is the first item out. Rather than push() and pop() methods, a queue has an enqueue() method for adding items and a dequeue() method for removing items.### Exercise: Creating Stacks and Queues

In this exercise, you will implement both the Stack and Queue data structures. Each data structure is stubbed out and commented with the instructions for what you need to complete.### Creating Stacks and Queues Solution

Bianca walks through the solution to the Creating Stacks and Queues exercise. he code for the solution is located on the "solutions" branch in the Github exercise repository.

## Recursion

### Why Recursion?

Recursion occurs when a function calls itself. Bianca makes a case for recursion and talks about why understanding the core concepts will make it easier to understand other use cases like recursive algorithms or recursive data structures.### Tracing Recursive Execution

Bianca explores a recursive function by tracing through each call. The callMe() function continues to call itself until the tracker variable satisfies the base case. If the function's base case is never reached, an infinite loop may occur.### Template for a Recursive Function

Bianca summarizes her recursion introduction by sharing the recipe for a recursive function. You identify the base case, identify the recursive case, return when appropriate, and write procedures that bring you closer to the base case.### Looping

In JavaScript, loops can be created with statements like for() and while(). A loop can also be created with a recursive function. Bianca walks through an example of loop implementing through the use of recursion.### Factorial with Loop

Using factorials as an example, Bianca first looks at how the factorial algorithm would be implemented with a for() loop. The loop starts at the number 2 and continues to multiply the numbers together until the desired factorial is reached. She will use this example as a baseline for implementing the recursive example.### Factorial with Recursion

Bianca now looks at the implementation of the factorial algorithm with recursion. The recursive computeFactorial(num) function continues to call itself while decrementing the num parameter. Once num is equal to one, the function returns and the results of all the calls on the stack are multiplied together.### Exercise: Recursion Interview Questions

In this exercise, you will implement a common recursion questions that are often asked during job interviews.### Recursive Reverse Solution

Bianca begins walking through the solution to the Recursion Interview Questions exercise. The first question she answers is how to implement a recursiveReverse() function. The code for the solution is located on the "solutions" branch in the Github exercise repository.### Recursive Multiplier Solution

Bianca continues her demonstration of the solution to the Recursion Interview Questions exercise by implementing the recursiveMultiplier() function. The code for the solution is located on the "solutions" branch in the Github exercise repository.### MinStack Solution

Now that recursion has been covered, Bianca jumps back to the Stacks & Queues exercise to demonstrate the solution to the MinStack object which contains a min() method that returns the minimum element in the stack. The code for the solution is located on the "solutions" branch in the Github exercise repository.### Implementing a Queue with Two Stacks Solution

Bianca continues working through the exercises left over from the Stacks & Queues topic. In this video, she looks at the solution to implementing a queue by using two stacks. The code for the solution is located on the "solutions" branch in the Github exercise repository.

## Time Complexity

### Space vs. Time Complexity

Time complexity helps developers understand an algorithm's performance. Time complexity can be influenced by how many comparisons are made or how many swaps are necessary to complete a task. Bianca spends a few minutes introducing time complexity and discussing how it compares to space complexity.### Calculating Time Complexity

Bianca uses a chart to plot the number of comparisons needed to complete various tasks. For example, how many comparisons would it take to determine the minimum value and the maximum value within a set of data. She uses these examples as a basis for understanding how time complexity is calculated.### Understanding Big-O

In computer science terms, time complexity is represented as "Big-O". The Big-O notation describes the performance of various algorithms as constant, logarithmic, linear, quadratic, or exponential. Bianca plots these Big-O calculations on a graph to illustrate their effect on space and time complexity.### Calculating Big-O of JS Operations

Bianca calculates the Big-O values for a few common JavaScript operations. She explores push(), pop(), incrementing a value, using a for() loop, and unshift(). With each operation, Bianca looks at how the Big-O value is calculated and its effect with larger data sets.### Calculating Big-O of Loops

Calculating the Big-O value of a group of operations can be more complex. Especially if the group contains nested loops or multiple statements. Bianca walks through how to calculated the Big-O value for two nested for() loops which increment values.### Exercise: Calculating Time Complexity

In this exercise, you will calculate the Time Complexity for various JavaScript code snippets. The code snippets for his exercise are located in Bianca's slides.### Calculating Time Complexity Solution

Bianca walks through the solution to the Calculating Time Complexity exercise.

## Elementary Sorting

### Bubble Sort

Bianca begins the sorting unit by demonstrating the Bubble Sort algorithm. Bubble Sort is a comparison sort which repeatedly swaps adjacent elements that are out of order. To help illustrate the process. Bianca shares a Bubble Sort demonstration video with Hungarian dancers. She also briefly pseudocodes the Bubble Sort algorithm.### Stability and Adaptability

A sorting algorithm can be described as stable if it preserves the order of equal items. The algorithm is adaptive if it becomes more efficient when the inputted data is already nearly sorted. Bianca spends a few minutes demonstrating stability and adaptability before moving on to the next sorting algorithm.### Selection & Insertion Sort

Bianca introduces Selection Sort and Insertion Sort. Selection Sort selects the smallest element in an array and pushes it into a new array. An in-place Selection Sort selects the largest element in the array and swaps it to the end of the array. Insertion Sort is similar to selection sort except it always selects the first element of the array and inserts it into the correct position in a new array.### Exercise: Bubble, Insertion, and Selection Sort

In this exercise, you will implement the elementary sorting algorithms covered in this section. These algorithms include Bubble Sort, Insertion Sort, and Selection Sort.### Bubble, Insertion, and Selection Sort Solution

Bianca walks through the solution to Bubble, Insertion, and Selection Sort exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository.

## Sorting Algorithms

### Merge Sort

The first complex sorting algorithm Bianca covers is Merge Sort. This algorithm takes a "divide and conquer" approach to sorting. After the data is separated into smaller lists, the merge step combines two sorted lists into one sorted list.### Pseudocoding the Merge Routine

To further illustrate the merge routine, Bianca pseudocodes the merge() method. This method takes a left list and a right list and merges to the two lists together. Since the left and right list are already sorted, the merge() method is able to insert the elements in the correct order so merged list is also sorted.### Pseudocoding Merge Sort

Bianca pseudocodes the full Merge Sort algorithm. The first step is to divide the input array into subarrays. The second step is to repeatedly merge the subarrays and sort them as they are merged. This process continues until all subarrays are merged into a single sorted array.### Time Complexity for Merge Sort

While looking at the pseudocode for the Merge Sort algorithm, Bianca breaks down each operation and calculates the time complexity. She also spends a few minutes looking at the full code solution for the Merge Sort algorithm to explain the recursive calls to the mergeSort() method.### Quick Sort Overview

The Quick Sort algorithm is similar to Merge Sort except that the bulk of the work is done while dividing the data. The Quick Sort algorithm selects a partition or pivot point. It then rearranges all the elements that are greater than the pivot to the right and all the elements less than the pivot to the left.### Understanding the Quick Sort Partition

While there are many ways to partition elements in the Quick Sort algorithm, Bianca gives a brief overview of the process. She also defines the terms "pivot point" and "pivot location" and describes the role they play as the Quick Sort algorithm sorts an array.### Pseudocoding Quick Sort Part 1

Bianca begins a lengthy pseudocode demonstration of the Quick Sort algorithm. In this first part, Bianca looks at how the pivot is initially selected and the pivot location is tracked as the algorithm loops through the array.### Pseudocoding Quick Sort Part 2

Bianca completes her pseudocode demonstration of the Merge Sort algorithm. In this part, she looks at swapping an element that is greater than the pivot.### Reviewing the Pseudocode

With the Quick Sort pseudocode complete, Bianca takes a few minutes to review the entire algorithm. She asks the audience to guide her through the pseudocode and apply the algorithm to a small array.### Debugging the Quick Sort Algorithm

As a bonus exercise, Bianca re-codes the Quick Sort partition() method with the group. As before, the partition method() is passed the array as well as first and last values. The first value is the pivot location. The last value is the pivot point. The method then proceeds to loop through the array to compare the elements to the pivot and make any necessary swaps.### Quick Sort Review Part 1

Bianca combines the quicksort() method with the partition() method to perform a full code review of the entire Quick Sort algorithm. She continues tracing through the code and documenting each swap as she fields questions from the audience.### Quick Sort Review Part 2

Bianca wraps up her coverage of the Quick Sort algorithm by finishing her full code review the partition() and quicksort() methods. She documents each step as an array is sorted.

## Trees & Searching

### Trees

Bianca introduces Trees and takes a look a what methods are required in the Tree interface. The constructor creates the storage and root properties. The Tree interface would contain methods like insert(), search(), min(), max(), and remove().### Linked Lists

A Linked List is a tree structure with only one child per node. Each child in the list contains a node value and a link to the next item in the list. To illustrate how Linked Lists work, Bianca shares a couple diagrams of the adding and removing of nodes.### Pseudocoding a Linked List

Bianca pseudocodes a Linked List. She creates a Node constructor for initializing Nodes. The Linked List constructor would instantiate Nodes for the head and tail. The Linked List object would also have methods for adding to the tail and removing nodes.### Exercise: Implement a Linked List

In this exercise, you will implement a Linked List. The code for this exercise is in the exercises Github repository. Comments are placed in the code under each method that needs to be implemented.### Implement a Linked List Solution

Bianca walks through the solution to the Implement a Linked List exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository.### Implementing a Tree

Now that Bianca has looked at the Linked List implementation, she spends a few minutes looking at how a Tree is implemented. The main difference between these two structures is a Tree cannot have any circular references. There is a root node in the tree and each node has a list of its children.

## Reviewing Core Concepts

### Review: Time Complexity

Bianca begins a unit which reviews all the topics she has covered up to this point. In this first video, she reviews Time Complexity. She looks at the Big-O calculations of common operations and reviews how to estimate the Big-O for any algorithm.### Review: Elementary Sorting

Bianca reviews the elementary sorting concepts she covered earlier in the course. She talks about stability vs. adaptability. She also reviews Bubble Sort, Insertion Sort, and Selection Sort.### Review: Recursion

Recursion is a common technique used throughout many sorting and searching algorithms. Bianca reviews some of the recursion topics covered earlier in the course.### Review: Merge Sort

Bianca reviews the Merge Sort algorithm. She reminds the group of the "divide and conquer" approach to sorting and reviews the merge routine.### Review: Quick Sort Part 1

In this two-part review of the Quick Sort algorithm, Bianca begins by looking back at how the partition routine functions. The partition routine chooses a pivot point and iterates the pivot location through the array swapping elements when necessary.### Review: Quick Sort Part 2

Bianca continues reviewing the Quick Sort algorithm by looking at the JavaScript implementations of the partition() and quicksort() methods. As with the other reviewed topics, she asks for some audience reflections at the end of the walk-through.### Review: Stacks & Queues

Bianca looks back at Stacks and Queues. Stacks implemented a last-in-first-out structure through the use of the push() and pop() methods. Queues use the dequeue() and enqueue() methods to implement a first-in-first-out structure.### Review: Linked Lists

Bianca reviews Linked Lists and demonstrates how they create ordered collections of nodes that are sequentially accessed and always contain a reference to the next node.### Review: Trees Part 1

In this two-part review of Trees, Bianca demonstrates how to add branches to a Tree through the use of the addChild() method.### Review: Trees Part 2

Bianca continues her review of Trees by diagramming the Tree structure she created in the first part.

## Binary Trees

### Binary Search Tree Overview

Trees have a parent-child relationship where a parent node can have any number of children. After reviewing the Tree structure, Bianca introduces a Binary Tree which adds a restriction that each node can only have two children. She then moves on to discuss Binary Search Trees which can be more performant than arrays since their nodes follow a specific structure.### Exercise: Binary Search Trees

In this exercise, you will create a Binary Search Tree. You will then implement the insert() and contains() methods.### Pseudocoding a Binary Search Tree

Bianca pseudocodes the constructor for a Binary Search Tree as well as the insert() method. The insert() method searches for the proper place to insert an element. If the value to be inserted is less than the current, the tree will move left. If the value is greater than the current, the tree will move right.### BST Search Procedure

A major part of a Binary Search Tree's insert() method is the search procedure. The insert() method must determine the property place for the inserted value. Bianca diagrams the BST search procedure by looking at the resulting tree after as different values are added.### BST Review & Scoping Discussion

Bianca spends a few minutes asking the audience about which parts of the BST insert and search procedures are the most confusing or difficult to grasp. While responding to some questions, she reviews the BST insertion process and explains the "this" keyword and the role scope plays in the process.### Pseudocoding the BST contains() Method

Bianca pseudocodes the Binary Search Tree contains() method. The contains() method will return true when the supplied value is found. If the value is not found in the current node, the contains() method will recursively call itself to explore the left or right branch. If the value does not exist in the tree, it will return false.### Binary Search Tree Exercise Solution

Bianca walks through the solution to the Binary Search Tree exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository.### In-Order Traversal

Searching through data structures like Arrays and Linked Lists are done with basic loops. A Binary Search Trees is more complex and is explored using in-order, pre-order, or post-order traversal. Bianca leads the audience in a short discussion about how the traversal of a BST might work before moving into a pseudocode example.### Pseudocoding In-Order Traversal Part 1

Bianca starts pseudocoding the in-order traversal algorithm for a Binary Search Tree. The in-order traversal algorithm will search to the left most node before traversing back to the right. Once the pseudocode is written, Bianca begins tracing out how it would execute with an example Binary Search Tree.### Pseudocoding In-Order Traversal Part 2

Bianca continues using the in-order traversal pseudocode to talk through an example Binary Search Tree. She traces out each step along the way and talks briefly about how in-order traversal compares to pre-order and post-order.### Pre-Order Traversal

With pre-order traversal, rather than traversing to the left-most node first, the algorithm begins with the current node. After the current node is visited both left and right children are visited. Bianca modifies the in-order pseudocode to become the pre-order algorithm to further examine this difference.### Post-Order Traversal

Post-order traversal will fully explore the left and right children of a node before return to examine the current node. After looking at the post-order pseudocode, Bianca summarizes Binary Search Tree traversal by comparing the in-order, pre-order, and post-order prototype implementations.### Initial Time Complexity for a BST

Before moving on to deleting BST nodes, Bianca leads the group through the process of calculating the time complexity for a Binary Search Tree. Search the tree is a logarithmic process. Traversing the tree would typically be linear.### Deleting Min/Max Nodes

Bianca begins talking about how to delete nodes from a Binary Search Tree. The first deletion algorithm she wants to implement is deleting the min or max value. Deleting the min value involves moving left until the left is null. Then set the left pointer of the parent to null.### BST Review

Before continuing with her min/max node deletion pseudocode, Bianca does a brief recap of Binary Search Trees.### Pseudocoding Min/Max Deletion

Bianca pseudocodes the deleteMin() method which deletes the minimum value of a Binary Search Tree. This method is passed the parent node to traverse. It moves left until the left pointer is null. Once the minimum value is reached, the parents left is set to null to delete the minimum node.### Reviewing the Min/Max Pseudocode Part 1

Bianca reviews the min/max deletion pseudocode by walking through each step in the execution. She looks at a couple different scenarios to make sure the code accounts for any edge cases.### Reviewing the Min/Max Pseudocode Part 2

Bianca continues her review of the min/max deletion pseudocode. She checks the code against an edge case where BST nodes only have right children.### Exercise: Deleting Single-Child Nodes

In this exercise, you will begin implementing the deleteNode() method. The deleteNode() method will search the tree for the passed value.### Deleting BST Nodes Solution Part 1

Bianca begins walking through the solution to the Deleting BST Nodes exercise. In the first part, she checks to see if the node is a leaf or if it has one child.### Deleting BST Nodes Solution Part 2

Bianca continues the solution to the Deleting BST Nodes exercise. She finishes the pseudocode for deleting nodes with a single child. If the deleted node has a child, that child will be set to either the left or the right pointer of the parent. The location depends on the deleted node's relationship to the parent.### Exercise: Deleting Two Children

In this exercise, you will complete the third case for deleting a node from a Binary Search Tree. The third case involves deleting a node that has two children.### Deleting Two Children Solution

Bianca walks through the solution to the Delete Two Children exercise. In the solution, a node with two children must have it's subtree searched for the smallest value. That value will be moved to the position of the deleted node.### Analysis of Time Complexity

Before moving to the next section, Bianca has a brief discussion about the time complexity of a Binary Search Tree. She also shares a few BST alternatives like AVL Trees, Red-Black Trees, and Splay Trees which may have better performance.

## Graphs & Paths

### Graph Vocabulary & Representations

A Graph is a collection of vertices connect by edges. A path is a sequence of connected vertices and a cycle is a path that is cyclical. Bianca outlines a few of these Graph vocabulary terms compares a Graph to an Adjacency Matrix.### Pseudocoding the Matrix Constructor

Bianca pseudocodes the constructor for a Graph. The main function of the constructor is to initialize the storage matrix.### Pseudocoding the addNode() Method

Next, Bianca pseudocodes the addNode() method for the Graph class. The addNode() method will determine how the node should be added and if a row or column is required in the matrix.### Pseudocoding the addEdges() Method

Finally, Bianca pseudocodes the addEdge() method. This method would receive the starting and ending vertices as parameters. Depending on if the matrix is directed or weighted, the matrix would then be updated to reflect the connection between to the vertices.### Exercise: Adding Nodes and Edges

In this exercise, you will implement the Graph pseudocode in JavaScript. You will create the constructor, addNode(), and addEdge() methods.### Adding Nodes and Edges Solution

Bianca walks through the solution to the Adding Nodes and Edges exercise.### Adjacency List

Finding paths and neighbors are easier to do with an Adjacency List. In an Adjacency List the connections for each node are provided. After introducing Adjacency Lists, Bianca answers a few audience questions about their representation.### Pseudocoding an Adjacency List

Bianca walks through the pseudocode for an Adjacency List. The constructor initializes the nodes array. The addNode() method adds the passed value ot the nodes array and the addEdges() method pushes the ending vertex to the starting vertices in the nodes array.### Exercise: Implement a Graph

In this exercise, you will implement the entire Graph class except for any removal or traversing methods.### Implement a Graph Solution

Bianca walks through the solution to the Implementing a Graph exercise. While she does not cover each method in the solution, the full codebase for the solution is located on the "solutions" branch in the Github exercise repository.

## Depth & Breadth-First Search

### Graph Traversing & Depth-First Search

Bianca gives a brief introduction to Graph traversal and depth first searching. Traversal algorithms help find paths, cycles, and connectivity. Depth-first search traverses to the bottom of the Graph before working its way back up and over to the other side.### Pseudocoding DFS Part 1

Bianca begins pseudocoding depth-first search. Before writing the pseudocode she diagrams the depth-first search procedure and what the recursive callstack might look like.### Pseudocoding DFS Part 2

Bianca continues pseudocoding the depth-first search algorithm. The base-case occurs when there is no longer any where to explore. Until the base-case is reached, the algorithm recursively loops through the edges. As nodes are explored, they must be flagged or marked as visited.### Breadth-First Search

Unlike depth-first search, breadth-first search will fully explore a level of the Graph before diving deeper. Bianca reviews the procedure for breadth-first search and explains the use of a queue for managing the discovered nodes.### Pseudocoding BFS

Bianca pseudocodes the breadth-first search algorithm. She also presents a few questions to the audience about how to get to the next layer and whether or not recursion is necessary.### Depth-First Search with a Graph Solution

Bianca looks and the final JavaScript solution for traversing a Graph with a depth-first-search. The code for the solution is located on the "solutions" branch in the Github exercise repository. Search the code for the Graph.prototype.traverseDepthFirst method.### DFS Graph Stack Trace Part 1

With the traverseDepthFirst() method implemented, Bianca tests it out by tracing out each step as it traverses a graph. With each iteration she duplicates the code and adds comments for what the next recursive call would be.### DFS Graph Stack Trace Part 2

Bianca continues tracing through her traversal of a Graph using the newly implemented traverseDepthFirst() method.### Depth-First Search with a Tree Solution

Bianca looks at the depth-first search algorithm for a Tree and compares the implementation to the Graph version. The code for the DFS Tree implementation is located in the Github exercise repository on the "solutions" branch.### Breadth-First Search Solution

Bianca shifts back to the breadth-first search algorithm and walks through the solution to the Graph implementation of breadth-first search. The code for the solution is located on the "solutions" branch in the Github exercise repository.### Breadth-First Search Stack Trace

Bianca uses the traverseBreadthFirst() algorithm to traverse through a graph. She traces each iteration through the queue to reinforce the differences between depth-first and breadth-first traversal.

## Hash Tables

### Hash Tables

A JavaScript Object is an example of a Hash Table because data is represented a key/value pairs. A hashing function can be used to map the key to an index by taking an input of any size and returning a hash code identifier of a fixed size.### Pseudocoding a Hashing Function

Bianca pseudocodes the basics of a hashing function. The hashing function must always return the same output for any given input. The returned value could be based on mathematical operations performed on the ASCII values of each character from the input string.### Key Components of a Hash Table

The key components of a hash table include a storage object as well as a hashing function. A hash table should also be able to get, set, and remove properties from the storage object. Bianca uses these key components to demonstrate how a hash table accesses objects in memory.### Pseudocoding set(), get(), & remove()

Bianca pseudocodes the constructor, set(), get(), and remove() methods for a hash table. The constructor would initialize the storage object and hashing function. The get() and set() methods would use the hashing function to access the specified data from the storage.### Handling Collisions

Bianca spends a few minutes talking about handling collisions. A collision may occur if a weak hashing function is used and values are stored at the same location. With most modern hashing functions, collisions should not be an issue.### Exercise: Implementing a Hash Table

In this exercise, you will implement a Hash Table. The starting code is located in the Github exercise repository. Comments are added to each method which needs to be implemented.### Implementing a Hash Table Solution

Bianca walks through the solution to the Implementing a Hash Table exercise. The code for the solution is located on the “solutions” branch in the Github exercise repository.### Next Steps

Bianca wraps up the course by sharing some ideas on where to go from here. She revisits each topic covered in this course and provides links for further reading or additional resources. These links can be found in the slides linked with this video. (edited)