DEV Community: Matt

What is a closure? Example use cases in JavaScript and React

Matt — Mon, 09 May 2022 15:02:51 +0000

What is a closure?

If you are not completely new to JavaScript and are unfamiliar with closures, you have probably used a closure without knowing it. A closure is when a function has access to variables (can read and change them) defined in its outer scope, even when the function is executed outside of the scope where it was defined. A closure is a function enclosing a reference (variable) to its outer scope. Functions can access variables outside of their scope.

Here is a simple example where an outer function that returns an inner function has access to a variable in the outer function:

function outerFunction() {
  let outerFuncVar = "outside";
  function innerFunction() {
    console.log(`The value is: ${outerFuncVar}`);
  }
  return innerFunction();
}

outerFunction();

Console output: The value is: outside

The outer function returns an inner function that "closes" over the outer function variable outerFuncVar. This is why it is called a closure. The outerFunction, which returns the innerFunction, can be called anywhere outside of its scope and the innerFunction will have access to, it can remember, the outerFuncVar. When it is called, it can read the value of this variable.

Let's modify the above example so that the outerFunction variable can be changed and new value is logged after 5 seconds has passed:

function outerFunction(input) {
  let outerFuncVar = input;
  function innerFunction() {
    setTimeout(() => {
      console.log(`The value is: ${input}`);
    }, 5000);
  }
  return innerFunction();
}

outerFunction("new value");

Console output: The value is: new value

Even after outerFunction has finished executing in the above example, the outerFuncVar is still accessible 5 seconds after the function was called. JavaScript automatically allocates memory when variables are initially declared. After a function returns, its local variables may be marked for garbage collection and removed from memory. Garbage collection is a type of automatic memory management used by JavaScript to free memory when an allocated block of memory, such as a variable and its value, is not needed anymore.

If the outerFuncVar was garbage collected right after the function call, it would cause an error because the outerFuncVar would no longer exist. The outerFuncVar is not garbage collected because JavaScript works out that the nested innerFunction may still be called as it is used in a closure. JavaScript does memory management for us, unlike low-level languages such as C.

You can also see this persistence of the closures reference to an outer variable by returning the innerFunction from the outerFunction and storing it in a variable before executing the innerFunction:

function outerFunction() {
  let outerFuncVar = "outside";
  function innerFunction() {
    console.log(`The value is: ${outerFuncVar}`);
  }
  return innerFunction;
}

const innerFunct = outerFunction();
innerFunct();

Console output: The value is: outside

If the outer function is a nested function itself , such as outerOuterFunction in the code below, all of the closures will have access to all of their outer function scopes. In this case the innerFunction closure has access to the outerFunction and outerOuterFunction variables:

function outerOuterFunction() {
  let outerOuterFuncVar = "outside outside";
  return function outerFunction() {
    let outerFuncVar = "outside";
    function innerFunction() {
      console.log(`The outerFunction value is: ${outerFuncVar}`);
      console.log(`The outerOuterFunction value is: ${outerOuterFuncVar}`);
    }
    return innerFunction;
  };
}

const outerFunct = outerOuterFunction();
const innerFunct = outerFunct();
innerFunct();

Console output:
The outerFunction value is: outside
The outerOuterFunction value is: outside outside

Multiple instances of a closure can also be created with independent variables that they close over. Let's look at a counter example:

function counter(step) {
  let count = 0;
  return function increaseCount() {
    count += step;
    return count;
  };
}

let add3 = counter(3); // returns increaseCount function. Sets step and count to 3
let add5 = counter(5); // returns increaseCount function. Sets step and count to 5

add3(); // 3
console.log(add3()); // 6

add5(); // 5
add5(); // 10
console.log(add5()); // 15

When the counter function is called using counter(3), an instance of the increaseCount function is created that has access to the count variable. step is set to 3, it's the function parameter variable, and count is set to 3 (count += step). It is stored in the variable add3. When the counter function is called again using counter(5), a new instance of increaseCount is created that has access to the count variable of this new instance. step is set to 5 and count is set to 5 (count += step). It is stored in the variable add5. Calling these different instances of the closure increments the value of count in each instance by the step value. The count variables in each instance are independent. Changing the variable value in one closure does not effect the variable values in other closures.

A more technical definition of a closure

A closure is when a function remembers and has access to variables in its lexical / outer scope even when the function is executed outside of its lexical scope. Closures are created at function creation time. Variables are organized into units of scope, such as block scope or function scope. Scopes can nest inside each other. In a given scope, only variables in the current scope or at a higher / outer scope are accessible. This is called lexical scope. Lexical, according to the dictionary definition, means relating to the words or vocabulary of a language. In this case, you can think of it as how scoping occurs in the JavaScript language. Lexical scoping uses the location of where a variable is declared in the source code to determine where the variable is available in the source code. Scope is determined at compile time, more specifically lexing time, by the compiler of the JavaScript Engine used to process and execute the code. The first stage of compilation involves lexing / parsing. Lexing is when the code is converted into tokens, which is part of the process of converting code into machine readable code. You can read about how the JavaScript engine works in this article: JavaScript Visualized: the JavaScript Engine.

Why are closures important? Some examples

Here are a few examples of where closures are used in JavaScript and React.

JavaScript

Async code

Closures are commonly used with async code, for example: sending a POST request using the Fetch API:

function getData(url) {
  fetch(url)
    .then((response) => response.json())
    .then((data) => console.log(`${data} from ${url}`));
}

getData("https://example.com/answer");

When getData is called, it finishes executing before the fetch request is complete. The inner function fetch closes over the url function parameter variable. This preserves the url variable.

Modules

The JavaScript module pattern is a commonly used design pattern in JavaScript to create modules. Modules are useful for code reuse and organization. The module pattern allows functions to encapsulate code like a class does. This means that the functions can have public and private methods and variables. It allows for controlling how different parts of a code base can influence each other. Closures are required for this, for functional modules. Functional modules are immediately invoked function expressions (IIFE). The IIFE creates a closure that has methods and variables that can only be accessed within the function, they are private. To make methods or variables public, they can be returned from the module function. Closures are useful in modules because they allow module methods to be associated with data in their lexical environment (outer scope), the variables in the module:

var myModule = (function () {
  var privateVar = 1;
  var publicVar = 12345;

  function privateMethod() {
    console.log(privateVar);
  }

  function publicMethod() {
    publicVar += 1;
    console.log(publicVar);
  }

  return {
    publicMethod: publicMethod,
    publicVar: publicVar,
    alterPrivateVarWithPublicMethod: function() {
      return privateVar += 2;
    },
  };
})();

console.log(myModule.publicVar); // 12345
console.log(myModule.alterPrivateVarWithPublicMethod()); // 3
myModule.publicMethod(); // 12346
console.log(myModule.alterPrivateVarWithPublicMethod()); // 5
console.log(myModule.privateVar); // undefined
myModule.privateMethod(); // Uncaught TypeError: myModule.privateMethod is not a function

Functional programming - currying and composition

Currying a function is when a function that takes multiple arguments is written in such a way that it can only take one argument at a time. It returns a function that takes the next argument, which returns a function that takes the next argument, ... this continues until all of the arguments are provided and then it returns value. It allows you to break up a large function into smaller functions that each handle specific tasks. This can make functions easier to test. Here is an example of a curried function that adds three values together:

function curryFunction(a) {
  return (b) => {
    return (c) => {
      return a + b + c;
    };
  };
}
console.log(curryFunction(1)(2)(3)); // 6

Composition is when functions are combined to create larger functions, it is an important part of functional programming. Curried functions can be composed into large, complex functions. Composition can make code more readable because of descriptive function names. The following is a simple example of currying and composition where there are two number functions (for simplicity): five and six that use the n function, which allows them to be called alone or composed with other functions such as the plus function. The isEqualTo function checks if two numbers are the same.

var n = function (digit) {
  return function (operator) {
    return operator ? operator(digit) : digit;
  };
};

var five = n(5);
var six = n(6);

function plus(prev) {
  console.log('prev = ', prev); // prev = 6
  return function (curr) {
    return prev + curr;
  };
}

function isEqualTo(comparator) {
  console.log('comparator = ', comparator); // comparator = 5
  return function (value) {
    return value === comparator;
  };
}

console.log(five()); // 5

// values calculated from the inside to the outside
// 1. six() => result1
// 2. plus(result1) => result2
// 3. five(result2) => final result
console.log(five(plus(six()))); // 11
console.log(isEqualTo(five())("5")); // false

You can read more about currying and composition in this article: How to use Currying and Composition in JavaScript.

Here is an example of a debounce function, from https://www.joshwcomeau.com/snippets/javascript/debounce/, that returns a function and makes use of a closure, like the counter example that we used earlier:

const debounce = (callback, wait) => {
  let timeoutId = null;
  return (...args) => {
    window.clearTimeout(timeoutId);
    timeoutId = window.setTimeout(() => {
      callback.apply(null, args);
    }, wait);
  };
};

Modern front end frameworks/libraries like React make use of a composition model where small components can be combined to build complex components.

React

Making hooks

Here is a function that mimics the useState hook. The initial value, the state getter, is enclosed in the closure and acts like stored state:

function useState(initial) {
  let str = initial;
  return [
    // why is the state value a function? No re-render in vanilla JavaScript like in React.
    // if you just use the value (no function), then change it with the setter function(setState) and then the log value, it will reference a "stale" value (stale closure) -> the initial value not the changed value
    () => str,
    (value) => {
      str = value;
    },
  ];
}

const [state1, setState1] = useState("hello");
const [state2, setState2] = useState("Bob");
console.log(state1()); // hello
console.log(state2()); // Bob
setState1("goodbye");
console.log(state1()); // goodbye
console.log(state2()); // Bob

To see a better implementation where the state value is not a function check out the following article - Getting Closure on React Hooks.

Closures remember the values of variables from previous renders - this can help prevent async bugs

In React, if you have an async function that relies on props that may change during the async function execution, you can easily end up with bugs if you use class components due to the props value changing. Closures in React functional components make it easier to avoid these types of bugs. Async functions, that use prop values, use closures to preserve the prop values at the time when the function was created. Each time a component renders, a new props object is created. Functions in the component are re-created. Any async functions that use variables from the props (or elsewhere), remember the variables due to closure. If the component that an async function is in is re-rendered and the props change (new values) during the async function call, the async function call will still reference the props from the previous render, where the function was defined, as the values were preserved due to closure. You can see an example of this in the article - How React uses Closures to Avoid Bugs.

Conclusion

We learned what closures are using some examples and saw some example use cases in JavaScript and React. To learn more about closures, you can check the articles linked below.

References / Further Reading

Implement Depth-First Search in a Binary Search Tree with JavaScript

Matt — Thu, 30 Dec 2021 15:55:46 +0000

Binary search trees are a useful data structure for storing data in an ordered format that makes searching for values, insertion and deletion quick. Real-world applications include their use in search algorithms, 3D game engines and graphics. In this article, we will learn about a type of tree traversal algorithm called depth-first search that can be used to explore a binary search tree. We will learn how to implement the 3 types of depth-first search algorithms: pre-order, in-order and post-order using recursion. Tree traversal algorithms are a common subject in coding interview questions.

What is a Binary Search Tree?

A tree is a type of data structure. It is non-linear, which makes it a good data structure to store and search for data. Search time in a linear data structure, such as an array or linked list, increases proportionally as the size of the data set increases. A tree data structure splits up the data, decreasing the search time.

A tree data structure, unsurprisingly, looks like a tree when visualized. Normally it looks like an upside-down tree. It is made up of nodes that store data. The nodes are connected by edges, also known as branches. A parent node branch connects to a child node. The first node in the tree is known as the root node. It is positioned at the top of the upside-down tree. The root is connected to subtrees. A Subtree refers to all of the descendants (children, grandchildren, ...) of a node. At the ends of the branches, the nodes that have no children are referred to as leaves.

Trees are recursive data structures. What this means is that each node (that is not a leaf) is a parent of its children and each child is a parent of its children, whose children are parents of its children and so on. We will see, later in this article, that recursion can be used for the algorithms used to traverse trees. There are iterative solutions using while loops, but the simplest solutions are recursive.

A binary tree is a particular type of tree where each node has, at most, 2 children. A binary search tree is a type of binary tree that has ordered nodes. For any node in the binary search tree, the values of the nodes in all of the left child subtree nodes are less than the value of the parent node. The values of the nodes in all of the right child subtree nodes are greater than or equal to the value of the parent node. This affects the insertion order when the tree is created. This can be seen in the diagram below.

Components of a binary search tree.

Why is a binary search tree useful?

Fast search, insert and delete

One measure of an algorithm's efficiency is its time complexity. It is an approximate measure of how long an algorithm takes to execute as the size of the data set, that the algorithm operates on, increases. The smaller the value, the better the algorithm. Time complexity is formally described using big O notation. You can think of the O as meaning "on the order of". It's a measure of the worst case for an algorithm. For example, a linear search algorithm (starts the search from the beginning of the data structure and checks each element sequentially) that searches for an element in a linked list or an array of size n will take ~O(n) steps. This is read as "big O of n" or "on the order of n". If there are 16 elements in the linear data structure, it will take 16 steps (worst case) to find the element using a linear search algorithm.

Binary search tree algorithms that search for an element in a binary search tree have a logarithmic run time, O(log n). This means that as the size of the data structure increases, the time taken for the operation increases logarithmically. This is much faster than a linear search. If there are 16 elements in a binary search tree. It will take O(log(16)) = 4 steps to find an element in a binary search tree. The logarithm is base 2. This difference becomes very pronounced as the data set size increases. If there are 1 048 576 elements. The linear search algorithm will take 1 048 576 steps to find an element in the worst case. The binary search tree algorithm will take 20 steps in the worst case.

Insertion and deletion are also quick in a binary search tree. When data is inserted, it is stored by reference. This means that a new piece of memory is created when it is a node is added to a binary search tree and it points to the parent node that it is connected to. The nodes can be spread out in memory. If you were to insert or delete an element from the middle of an array, many operations would need to be performed to shift the values in the array. This is because values in an array are all next to each other in memory.

Why is the search time in a binary search tree logarithmic?

A logarithm is defined as the inverse function to exponentiation. What this means is that if you have a logarithm, say log2(16). You can get the answer by asking: "What power do I have to raise 2 to get an answer of 16?". This can be written as 2^? = 16. Divide and conquer algorithms that continually divide a data structure in half are logarithmic (base 2). This includes binary search tree algorithms. Logarithms that are base 2 can be considered as divisions by 2.

log2(16) = 4 can be read as: "I have to raise 2 to the power of 4 to get an answer of 16". This is equivalent to: "16 requires 4 divisions by 2 to reach a value of 1".

16 / 2 = 8 -> 8 / 2 = 4 -> 4 / 2 = 2 -> 2 /2 = 1.

For example, if you have 16 elements in a binary search tree, like in the image below, the time complexity is O(log n). This means it will take O(log(16)) or 4 steps, in the worst case, to find an element. This is equal to the height of the tree. When searching for an item, starting at the root, the correct direction, left or right, can be chosen at each step because the nodes are ordered. At each step, the number of nodes to search is halved. The problem size is halved with each step.

Binary search tree. The height is equal to the logarithm (base 2) of the number of nodes. For each node traversed in the tree, the number of nodes remaining to search is halved.

The binary search trees used in this article are balanced. This means that the nodes are spread out well. The height of a tree is the number of nodes between the root node and a leaf node. A tree may have many different heights. If the difference between the maximum height and minimum height is 1 or 0, then the tree is balanced.

Logarithmic search times occur for balanced trees. The more unbalanced a binary search tree becomes, the slower the search time. The search time becomes more linear as the tree starts to become more linear (O(n)). There are self-balancing trees that can be used for dynamic data sets. This is beyond the scope of this article - you can read more about them in this Wikipedia article: Self-balancing binary search tree.

The more unbalanced a binary search tree becomes, the more it starts to resemble a linear data structure. The search time also increases.

Exploring a binary search tree: Depth-first search

Various algorithms allow you to visit each node in a tree instead of searching for a specific value. These algorithms are used to explore the data: each node's value is read and can be checked or updated. They can be broadly divided into depth-first and breadth-first search.

Breadth-first, also known as level-order, search algorithms read the value of all the nodes at a particular level in a tree before moving on to the next level. The progression of the algorithm as it traverses the tree and reads the node values is breadth-first. It starts at the root node and moves down the tree level by level.

Breath-first search in a binary search tree.

Depth-first search algorithms first read all of the node values in a particular subtree. The subtree is traversed deeply, all the way to the bottom leaves, before moving on to the next subtree. We will explore depth-first search algorithms in more detail.

There are 3 types of depth-first search: pre-order, in-order and post-order. In these algorithms, the root, the left subtree of the root and the right subtree of the root are traversed. The difference between them is the order in which the node values are read:

pre-order: root -> left subtree -> right subtree
in-order: left subtree -> root -> right subtree
post-order: left subtree -> right subtree -> root

Depth-first search in a binary search tree. The 3 types of search algorithms are shown: pre-order, in-order and post-order.

In pre-order search, the root value is read first and then the subtree values are read. In in-order search, the first node read is the left-most node in the BST. The last node read is the right-most node in the BST. In post-order search, the leaves are read first and then the roots are read.

Let's explore how this traversal occurs through each node. The following CodePen shows the three types of depth-first search tree traversal algorithms. Click on the buttons to visualize the traversal and see the order in which the nodes are visited and read. Notice that in-order traversal prints the values of the nodes in order.

CodePen showing depth-first search tree traversal algorithms in a binary search tree. Modified from: https://codepen.io/mehmetakifakkus/pen/bqVjXX

Implement depth-first search in JavaScript

Let's implement the 3 types of depth-first search algorithms. The inspiration for writing this article came from doing a freeCodeCamp challenge on using depth-first search in a binary search tree. You can try the challenge before continuing.

The implementations used here make use of recursive functions. This means that the functions call themselves. The recursion stops when the base case is reached. In the depth-first search algorithms implemented here, the root node is passed in as an argument to the recursive algorithm function. Its left child or right child is recursively passed in as an argument to the same function. The left and right children are subtrees of the parent node. The recursion stops when the left node and the right node of the node being traversed is null. In other words, when a node with no children, a leaf, is reached. During the recursion, the value of the current node is added to an array. The output of the algorithms is an array of the visited nodes. The order of the array elements is equal to the order in which the nodes were read.

The code below will be used as a base for implementing the algorithms. We will implement the algorithms as methods within a BinarySearchTree function. There is an add method that will be used to add nodes to the tree when we test the algorithm. The Node function is used by the add method to create nodes. There is also a displayTree function that will be used to visualize the tree, as a string, in the console. For simplicity, no duplicate values will be allowed in the binary search tree. From now on, binary search tree will be abbreviated as BST.



// converts created binary search tree into a JSON string
// JSON.stringify(value, replacer, space)
// tree will be the passed in BST
// null means that all properties are included in the JSON string
// 2 adds some white space to the JSON string output to make it more readable
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));

function Node(value) {
  // give node a value
  this.value = value;
  // node has no children initially
  this.left = null;
  this.right = null;
}

function BinarySearchTree() {

  // root is initially empty - no nodes
  this.root = null;

  // add node to tree
  // value and current node (currNode) passed in as arguments
  // the default value of currNode is this.root
  this.add = (value, currNode = this.root) => {
    // create a new node
    let newNode = new Node(value);
    // if no nodes in tree, make newly added node the root
    if(!this.root) {
      this.root = newNode;
    } else {
      // no duplicate values allowed - for simplicity 
      if (value === currNode.value) {
        return null;
      // add node to left subtree
      } else if (value < currNode.value) {
        // if no left child, add new node as left child - base case
        // else recursively call add() again - currNode changes - moving down tree
        !currNode.left ? currNode.left = newNode : this.add(value, currNode.left);
      // add node to right subtree
      } else {
        !currNode.right ? currNode.right = newNode : this.add(value, currNode.right);
      }
    }
  }

}

The 3 algorithms for pre-order, in-order and post-order are very similar. They will be added as methods to BinarySearchTree. They all share the following code:



 this.method = () => {
    if (this.root === null) {
      return null;
    } else {
      let values = [];
      function traversefunction(currNode) {
        // different for each method
      }
      traversefunction(this.root);
      return values;
    }
  }

The first thing we check is if the root is null, which would mean the BST has no nodes. If this is the case we return null as there is no BST to traverse. The output of the method is stored in the value array and is returned from the function.

Each method has a traverse function used to traverse the tree. It is initially called with the root node as an argument. These traversal functions are recursively called to traverse the BST tree. These traversal functions are where the methods differ. The traversal functions differ in the order of execution of the current node value being pushed into the array.



// PRE-ORDER

// add current node value
values.push(currNode.value);
// if left child node exists - traverse left subtree
currNode.left && traversePreOrder(currNode.left);
// if right child node exists - traverse right subtree
currNode.right && traversePreOrder(currNode.right);

// IN-ORDER

// if left child node exists - traverse left subtree
currNode.left && traversePreOrder(currNode.left); 
// add current node value
values.push(currNode.value); 
// if right child node exists - traverse right subtree
currNode.right && traversePreOrder(currNode.right);

// POST-ORDER

// if left child node exists - traverse left subtree
currNode.left && traversePreOrder(currNode.left); 
// if right child node exists - traverse right subtree
currNode.right && traversePreOrder(currNode.right); 
// add current node value
values.push(currNode.value);

Before we continue with explaining each method in detail, let's briefly learn about the call stack so that we can better understand the recursive function calls in the algorithms.

What is the call stack?

A call stack is a mechanism used by the JavaScript Engine interpreter to keep track of function calls. The JavaScript engine is the program that reads, interprets, optimizes and executes JavaScript code. It converts human-readable JavaScript code into machine-readable code. When a function is called, the JavaScript Engine interpreter adds it to the top of the call stack and starts executing the function. If the function calls another function, which may be the same function (recursive function call), the newly called function is added to the top of the call stack. The call stack uses the last-in-first-out (LIFO) principle. When the current function, which is at the top of the call stack, completes its execution it is popped off the call stack. A functions execution is complete when it returns a value or reaches the end of its scope. The interpreter then resumes execution of the code from where it left off on the call stack, which is the function that is now at the top of the call stack. The GIF below shows an example of how function calls are added and removed from the call stack. This example does not show, for simplicity, the execution of the main function, which is the execution of the whole script. You can read more about the call stack in this article: JavaScript Event Loop And Call Stack Explained.

Simplified example showing how functions are added and removed from the call stack during code execution.

Pre-order

Let's Implement the preOrder method. In your code editor or your browser dev tools add the displayTree, Node and BinarySearchTree functions from the code above. Add the preorder method, displayed in the code below, to the BinarySearchTree function:



  this.preOrder = () => {
    if (this.root === null) {
      return null;
    } else {
      let values = [];
      function traversePreOrder(currNode) {
        values.push(currNode.value); // add current node (subtree root)
        currNode.left && traversePreOrder(currNode.left); // traverse left subtree
        currNode.right && traversePreOrder(currNode.right); // traverse right subtree
      }
      traversePreOrder(this.root);
      return values;
    }
  }

At the bottom of the script, add the code displayed below. We create a new BST called testBST, it is an instance of the BinarySearchTree object that contains the preOrder and add method. Then we add nodes to it using the add method. The BST has the same nodes as the interactive CodePen BST shown earlier.

We then console log the the created BST to visualize it using the displayTree function and then console log the preorder method to see its output.



var testBST = new BinarySearchTree();
testBST.add(5);
testBST.add(3);
testBST.add(2);
testBST.add(4);
testBST.add(8);
testBST.add(6);
testBST.add(9);
console.log('Binary search tree: ',JSON.stringify(testBST.root, null, 2));
console.log('Binary search tree: pre-order search ', testBST.preOrder());

The output of the console logs should be:



binary search tree:  {
  "value": 5,
  "left": {
    "value": 3,
    "left": {
      "value": 2,
      "left": null,
      "right": null
    },
    "right": {
      "value": 4,
      "left": null,
      "right": null
    }
  },
  "right": {
    "value": 8,
    "left": {
      "value": 6,
      "left": null,
      "right": null
    },
    "right": {
      "value": 9,
      "left": null,
      "right": null
    }
  }
}

Binary search tree: pre-order search  Array(7) [ 5, 3, 2, 4, 8, 6, 9 ]

You can compare the console logged BST JSON string to the BST in the CodePen example, the trees are the same. The output of the pre-order search also matches the output of the pre-order search in the CodePen example.

Now let's go through the execution of the function calls step by step to understand the traversal, order of the recursive function calls and the order in which the values are read and added to the values array. The following slide show shows how the traversePreOrder function within the preOrder method is recursively called. It shows how the recursively called traversePreOrder function is added to and removed from the call stack during the execution of the preOrder method. The BST traversal is visually shown in the middle. The addition of node values to the values array is shown at the bottom left. Note that the stack continues to grow until a leaf node is reached, the maximum stack height occurs when a leaf is reached. The maximum stack height of the traversePreOrder functions (ignoring the preOrder function on the stack) is 3, which is equal to the height of the BST. The space complexity of the tree is O(h), where h is the height of the tree. We learnt earlier that an algorithm's time complexity is an approximate measure of how long an algorithm takes to execute as the size of the data set, that the algorithm operates on, increases. An algorithm's space complexity is an approximate measure of how much memory is needed to execute the algorithm as the size of the data set increases.

Execution of the `preOrder` method. The recursive calls of the `traversePreOrder` function are shown alongside the traversal of the Binary Search Tree as each line of code is executed.

In-order

Let's Implement the inOrder method. In the code you used for the preOrder method, add the following inOrder method to the BinarySearchTree function:



  this.inOrder = () => {
    if (this.root === null) {
      return null;
    } else {
      let values = [];
      function traverseInOrder(currNode) {
        currNode.left && traverseInOrder(currNode.left);
        values.push(currNode.value);
        currNode.right && traverseInOrder(currNode.right);
      }
      traverseInOrder(this.root);
      return values;
    }
  }

Add the following console log at the end of the script to test the method:



console.log('Binary search tree: in-order search ', testBST.inOrder());

The output of the added console log should be:



Binary search tree: in-order search  Array(7) [ 2, 3, 4, 5, 6, 8, 9 ]

Now let's go through the execution of the function calls step by step to understand the algorithm. The following slide show shows how the traverseInOrder function is recursively called. If you compare the call stack execution to the traversePreOrder function in the previous section, you will notice that the order of recursive function calls is the same. The point at which the current node value is pushed into the values array differs. This is the same for the traversePostOrder method that will be described in the next section.

Execution of the `inOrder` method. The recursive calls of the `traverseInOrder` function are shown alongside the traversal of the Binary Search Tree as each line of code is executed.

Post-order

Let's Implement the last method, the postOrder method. Add the following. Add the following postOrder method to the BinarySearchTree function:



  this.postOrder = () => {
    if (this.root === null) {
      return null;
    } else {
      let values = [];
      function traversePostOrder(currNode) {
        currNode.left && traversePostOrder(currNode.left);
        currNode.right && traversePostOrder(currNode.right);
        values.push(currNode.value);
      }
      traversePostOrder(this.root);
      return values;
    }
  }

Add the following console log at the end of the script to test the method:



console.log('Binary search tree: post-order search ', testBST.postOrder());

The output of the added console log should be:



Binary search tree: post-order search  Array(7) [ 2, 4, 3, 6, 9, 8, 5 ]

Now let's go through the execution of the function calls step by step to understand the algorithm. The following slide show shows how the traversePostOrder function is recursively called.

Execution of the `postOrder` method. The recursive calls of the `traversePostOrder` function are shown alongside the traversal of the Binary Search Tree as each line of code is executed.

Conclusion

Binary search trees are a useful data structure that can be explored using depth-first search algorithms. The 3 types of depth-first search algorithms: pre-order, in-order and post-order can be implemented using recursion. They are very similar algorithms, they only differ in the order in which the node values are read. Understanding these algorithms can help you pass your next coding interview and you may even find yourself using them in a real-world application.

Here are some useful links for further study:

1) freeCodeCamp Coding Interview Prep - Data Structures

2) JavaScript Event Loop And Call Stack Explained

3) Python tutor: Visualize execution of code (Python, Java, C, C++, JavaScript, or Ruby) - line by line

How to rate limit a login route in Express using node-rate-limiter-flexible and Redis

Matt — Mon, 31 May 2021 20:09:37 +0000

Introduction

Rate limiting is a method used for controlling network traffic. It limits the number of actions a user can make per unit of time ¹. In this tutorial, we will rate limit a login route to help protect it from brute force attacks. This limits the number of password guesses that can be made by an attacker. We'll use the npm package node-rate-limiter-flexible to count and limit the number of login attempts by key. Each key will have a points value that will count the number of failed login attempts. The keys will expire after a set amount of time. The key-value pairs will be stored in Redis, which is an open-source in-memory data structure store. It has many different use cases. We will use it as a simple database. Redis is simple to use and very fast. We'll create an online instance of Redis, connect it to an express application, and then use the Redis command-line interface (redis-cli) to view the database. A prerequisite for this tutorial is an ExpressJS application with a login route and user authentication.

Express application with rate limiting on the login route. The key for a particular user stores the number of failed logins. If the number of failed logins exceeds the set maximum number of failed logins, then the route will be blocked. The keys expire after a set amount of time.

We will use two types of keys to count the number of failed logins. One will be a string made using the user's IP address. The other will be a string made by joining the user's email address and IP address. When a user attempts to log in, if the user exists and the password is not correct, the two keys will be created for the user.

For example, the keys stored in Redis may look like this after a failed login attempt where the password was incorrect:

key 1: "login_fail_ip-192.168.1.1" : 1
key 2: "login_fail_username_and_ip-example@example.com_192.168.1.1" : 1

Prerequisites

Express app with login route and login authentication (login with username or email)
Registered users stored in a database

Set up the rate-limiting middleware

Middleware used that is not necessary for rate-limiting

This example is from an Express application that uses MongoDB as a database to store the users' data. The following libraries, which will be used in this example, are not necessarily required to set up login rate limiting.

passport - authentication middleware
util.promisify() - a method defined in the utilities module of the Node.js standard library. It converts methods that return responses using a callback function to instead return responses in a promise object. The syntax is much cleaner.
connect-flash - middleware for flash messages notifying a user if the login was successful or not

Submitted data on the request.body is parsed as a JSON object by the built-in middleware function in Express: Express.json(). The data is stored in JSON format as it is a commonly used, organized, and easily accessible text-based format ².

These were added as application-level middleware in app.js using app.use().

Rate-limiting middleware

The rate-limiting middleware used is a modification of the node-rate-limiter-flexible library example of how to protect a login endpoint. This rate-limiting middleware is written for an Express application using a Redis store, but the same idea can be applied to rate-limiting middleware with other Node.js frameworks such as Koa, Hapi, and Nest or a pure NodeJS application ³. We'll create 2 rate limiters. The first blocks the login route, for one hour, after 10 consecutive failed login attempts. The failed login counts are reset after a successful login. Rate limiting is based on the user's email address and IP address. The second blocks the login route, for one day, after 100 failed login attempts. Rate limiting is based on the user's IP address. After this middleware is set up, we will set up the Redis database.

You can simply rate limit based on IP address only, the problem with this is that IP addresses are not always unique ⁴. A user in a network that shares a public IP address could block other users in that network. If you limit based on email address only, then a malicious user could block someone's access to the application by simply sending many requests to log in. Blocking by email address and IP address adds some flexibility. A user may be blocked using one IP address but could try login from another device. It is important to note that most devices use a dynamic IP address that changes over time and that IP addresses can be modified ⁵^,⁶. Rate-limiting aims to minimize brute force attacks to guess a user's password. When rate limiting, user experience also needs to be considered. Being too strict by blocking users after only a few attempts is not good for the user experience. You need to make a trade-off between security and user experience.

npm packages required for Redis connection and rate-limiting

Rate limit controller

Create a file for the rate-limiting middleware. For example, rateLimitController.js.

In this controller that will handle the login route POST request, a connection to Redis will be set up. Then a rate limiter instance that counts and limits the number of failed logins by key will be set up. The storeClient property of the rate limiter instance will link the rate limiter instance to a Redis database (redisClient) that will be set up later. A points property on the rate limiter instance determines how many login attempts can be made. Keys are created on the instance by using the IP address of the login request or the IP address and email address. When a user fails to log in, points are consumed. This means the count for the key increases. When this count exceeds the points property value, which is the maximum number of failed login attempts allowed, then a message is sent to the user that states that too many login attempts have been made. The keys only exist for a defined amount of time, after this time the rate-limiting is reset. A variable, retrySecs, will be created to determine when a user can try to log in again. The time remaining until another login can be attempted is determined by using the msBeforeNext() method on the rate limiter instance.

If the login route is not being rate-limited, then we will authenticate the user. In this tutorial, Passport is used. If the authentication fails and the user's email exists, then a point will be consumed from each rate limiter instance. If authentication is successful the key for the current user, based on IP address and email address, will be deleted and the user will be logged in. A login session is established using the Passport.js method logIn().



const redis = require('redis');
const { RateLimiterRedis } = require('rate-limiter-flexible');
const passport = require('passport');

// create a Redis client - connect to Redis (will be done later in this tutorial)
const redisClient = redis.createClient(process.env.REDIS_URL, {
  enable_offline_queue: false
});

// if no connection, an error will be emitted
// handle connection errors
redisClient.on('error', err => {
  console.log(err);
  // this error is handled by an error handling function that will be explained later in this tutorial
  return new Error();
});

const maxWrongAttemptsByIPperDay = 100;
const maxConsecutiveFailsByEmailAndIP = 10; 

// the rate limiter instance counts and limits the number of failed logins by key
const limiterSlowBruteByIP = new RateLimiterRedis({
  storeClient: redisClient,
  keyPrefix: 'login_fail_ip_per_day',
  // maximum number of failed logins allowed. 1 fail = 1 point
  // each failed login consumes a point
  points: maxWrongAttemptsByIPperDay,
  // delete key after 24 hours
  duration: 60 * 60 * 24,
  // number of seconds to block route if consumed points > points
  blockDuration: 60 * 60 * 24 // Block for 1 day, if 100 wrong attempts per day
});

const limiterConsecutiveFailsByEmailAndIP = new RateLimiterRedis({
  storeClient: redisClient,
  keyPrefix: 'login_fail_consecutive_email_and_ip',
  points: maxConsecutiveFailsByEmailAndIP,
  duration: 60 * 60, // Delete key after 1 hour
  blockDuration: 60 * 60 // Block for 1 hour
});

// create key string
const getEmailIPkey = (email, ip) => `${email}_${ip}`;

// rate-limiting middleware controller
exports.loginRouteRateLimit = async (req, res, next) => {
  const ipAddr = req.ip;
  const emailIPkey = getEmailIPkey(req.body.email, ipAddr);

  // get keys for attempted login
  const [resEmailAndIP, resSlowByIP] = await Promise.all([
    limiterConsecutiveFailsByEmailAndIP.get(emailIPkey),
    limiterSlowBruteByIP.get(ipAddr)
  ]);

  let retrySecs = 0;
  // Check if IP or email + IP is already blocked
  if (
    resSlowByIP !== null &&
    resSlowByIP.consumedPoints > maxWrongAttemptsByIPperDay
  ) {
    retrySecs = Math.round(resSlowByIP.msBeforeNext / 1000) || 1;
  } else if (
    resEmailAndIP !== null &&
    resEmailAndIP.consumedPoints > maxConsecutiveFailsByEmailAndIP
  ) {
    retrySecs = Math.round(resEmailAndIP.msBeforeNext / 1000) || 1;
  }

  // the IP and email + ip are not rate limited  
  if (retrySecs > 0) {
    // sets the response’s HTTP header field
    res.set('Retry-After', String(retrySecs));
    res
      .status(429)
      .send(`Too many requests. Retry after ${retrySecs} seconds.`);
  } else {
    passport.authenticate('local', async function(err, user) {
      if (err) {
        return next(err);
      }
           if (!user) {
        // Consume 1 point from limiters on wrong attempt and block if limits reached
        try {
          const promises = [limiterSlowBruteByIP.consume(ipAddr)];
          // check if user exists by checking if authentication failed because of an incorrect password
          if (info.name === 'IncorrectPasswordError') {
            console.log('failed login: not authorized');
            // Count failed attempts by Email + IP only for registered users
            promises.push(
              limiterConsecutiveFailsByEmailAndIP.consume(emailIPkey)
            );
          }
          // if user does not exist (not registered)
          if (info.name === 'IncorrectUsernameError') {
            console.log('failed login: user does not exist');
          }

          await Promise.all(promises);
          req.flash('error', 'Email or password is wrong.');
          res.redirect('/login');
        } catch (rlRejected) {
          if (rlRejected instanceof Error) {
            throw rlRejected;
          } else {
            const timeOut =
              String(Math.round(rlRejected.msBeforeNext / 1000)) || 1;
            res.set('Retry-After', timeOut);
            res
              .status(429)
              .send(`Too many login attempts. Retry after ${timeOut} seconds`);
          }
        }
      }
      // If passport authentication successful
      if (user) {
        console.log('successful login');
        if (resEmailAndIP !== null && resEmailAndIP.consumedPoints > 0) {
          // Reset limiter based on IP + email on successful authorisation
          await limiterConsecutiveFailsByEmailAndIP.delete(emailIPkey);
        }
        // login (Passport.js method)
        req.logIn(user, function(err) {
          if (err) {
            return next(err);
          }
          return res.redirect('/');
        });
      }
    })(req, res, next);
  }
};

Extra notes

Within the RedisClient, the property enable_offline_queue is set to false. This is done to prevent issues such as slowing down servers if many requests are queued due to a Redis connection failure. The author of node-rate-limiter-flexible recommends this setting unless you have reasons to change it ⁷.

req.ip contains the remote IP address of the request ⁸. If you are using the Express app behind a reverse proxy, such as Cloudflare CDN, then you should set the Express apps trust proxy setting to true and provide the IP address, subnet, or an array of these that can be trusted as a reverse proxy. If you do not do this, the value of req.ip will be the IP address of the reverse proxy ⁹. Also note that running your application locally during development, req.ip will return 127.0.0.1 if you are using IPv4 or ::1, ::fff:127.0.0.1 if you are using IPv6 ¹⁰. These describe the local computer address.

In index.js, the file with all of your routes. The following route is defined:



router.post('/login', catchErrors(rateLimitController.loginRouteRateLimit));

catchErrors is an error handling function that is used to catch any async-await errors in the controller. This error handling method is from the Wes Bos course Learn Node.

The errors for a Redis connection failure are handled as follows: Node Redis returns a NR_CLOSED error code if the client's connection dropped. ECONNRESET is a connection error. You can also set up a retry strategy for Node Redis to try and reconnect if the connection fails ¹¹.



  if (err.code === 'NR_CLOSED' || err.code === 'ECONNRESET') {
    req.flash('error', 'There was a connection error');
    res.redirect('back');

Set up Redis

The code above will not work yet as there is no Redis database set up. We will create a Redis database in the cloud using Redis Labs. We will use the free plan. Then we will connect to this database through our Express app. To view the database, we will download Redis locally so that we can use the built-in client redis-cli (command-line interface). We will download and use Redis using Windows Subsystem for Linux (WSL), which allows you to use a Linux terminal in Windows. Other methods are described on the Redis website download page.

Create an account with Redis Labs

Create an account on the Redis Labs website. Follow the instructions in the documentation to learn how to create a database.

Connect the Redis instance on Redis Labs with your Express application

In your express application variables.env add the REDIS_URL:

REDIS_URL=redis://<password>@<Endpoint>

Your Endpoint and password can be found in the database in the Configuration details of the View Database screen:

The Endpoint setting shows the URL for your database and the port number.
The Access Control & Security setting shows the password.

In the rate limit controller from the previous section, the following code connects the cloud Redis instance, hosted on Redis Labs, to the Express application:



const redisClient = redis.createClient(process.env.REDIS_URL, {
  // if no connection, an error will be emitted
  enable_offline_queue: false
});

The rate limiter instances connect to the cloud Redis instance as follows (also from the rate limit controller):



const limiterSlowBruteByIP = new RateLimiterRedis({
  storeClient: redisClient,

...

const limiterConsecutiveFailsByUsernameAndIP = new RateLimiterRedis({
  storeClient: redisClient,

...

Set up WSL and download Redis

You will be able to rate limit your login route now, the next step is to set up Redis locally so that we can view the Redis database using the Redis command-line interface (redis-cli). Redis works best with Linux. Linux and OS X are the two operating systems where Redis is developed and tested the most. Linux is recommended for deployment ^{12, 13}.

You can follow this article on how to set up WSL, download and install a supported Linux distro and install Redis locally. Install Redis somewhere outside of your application. The Linux distro used in this tutorial is Ubuntu 18.04.

Connect the redis-cli to the Redis instance on Redis Labs

We will use the redis-cli locally to see the key-value pairs created. Run your Express application and in a WSL terminal run the redis-cli:

cd into the Redis folder that you downloaded

cd redis-6.2.3

make sure the server is running

sudo service redis-server start

to stop the server: sudo service redis-server stop

If you run redis-cli, you will connect to the local instance of Redis and will run locally on the Localhost (127.0.0.1:6379). To exit, run quit. To connect the redis-cli to the cloud instance of the Redis Labs database that we created, we'll use the URL-based connection method from the Redis Labs docs. This connects to the Redis database using an endpoint URL and port number. Check the database Configuration details in the View Database screen to find the endpoint url and password.



$ redis-cli -h redis-19836.c9.us-east-1-2.ec2.cloud.redislabs.com
-p 19836 -a astrongpassword

h is the host: add your endpoint, without the port number
p is the port, which is shown at the end of the endpoint url
a is access control. Add your password

You can test if the connection worked by typing PING. If the connection worked redis-cli will return PONG.

if the response is NOAUTH Authentication required - check that you typed the password correctly. You can run quit to exit the redis-cli so that you can try again.

Basic Redis commands

There are many commands available as shown in the docs. For our use case, we only need to know a few simple commands. You can try them in the redis-cli that is connected to your Redis Labs Redis instance. Note that the commands are all uppercase in the Redis docs, but the commands are not case-sensitive. However, key names are case-sensitive.

PING

Checks the connection to the Redis database. If there is a connection, PONG will be returned.

SET

Set the string value of a key. It is used to create a key-value pair or change the value of an existing key.



> SET job teacher
OK

This sets the key "job" to the value "teacher". The response OK means that the command was successful.

MSET

Like SET, but its sets the values of multiple keys.



> MSET job "teacher" AGE "50" TITLE "Mr."
OK

GET

Get the value for a key.



> GET job
"teacher"

MGET

Get the value of multiple keys.



> MGET job age title
1) "teacher"
2) "50"
3) "Mr."

DEL

Deletes a specific key.



> DEL job
(integer) 1 -> this means that it found a key with the name "job" and deleted it.

If you try :



> GET job
(nil) -> this means that no key with the name "job" exists.

SCAN

View all keys. It iterates over a collection of keys. It is a cursor-based iterator. If you want to view all entries then run



> SCAN 0
1) "0"
2) "age"
3) "title"

The first value returned is "0", which indicates that a full iteration occurred. This means that all of the keys in the database were scanned. For more details, you can read up the description of the SCAN command in the docs.

If you want to view all keys, excluding the first key then run SCAN 1.

FLUSHALL

This deletes all of the keys in the database.

CLEAR

Clears the terminal.

Test the rate-limiting

We are going to test one of the rate limiters. Run your application locally and connect to Redis labs via the redis-cli in a WSL terminal. Before starting, make sure all of the keys in your database are deleted by running the command FLUSHALL. In your rate limit controller middleware (rateLimitController.js.), set maxConsecutiveFailsByEmailAndIP to 3. Set the options duration and blockDuration of limiterConsecutiveFailsByEmailAndIP to 60. This will allow us to test the rate-limiting quickly.



...

const maxConsecutiveFailsByEmailAndIP = 3; 

...

const limiterConsecutiveFailsByEmailAndIP = new RateLimiterRedis({
  storeClient: redisClient,
  keyPrefix: 'login_fail_consecutive_email_and_ip',
  points: maxConsecutiveFailsByEmailAndIP,
  duration: 60 
  blockDuration: 60  
});

...

Failed login with an account that does not exist

Try login using an email (or another user identifier, such as user name, used in your app) that does not exist (not registered).

After this, in the redis-cli, that is connected to your cloud Redis instance hosted on Redis Labs, view all of the keys.



yourRedisLabsEndpoint> SCAN 0
1)"0"
2) "login_fail_ip_per_day:::1"

On localhost, req.ip will return 127.0.0.1 if you are using IPv4 or ::1, ::fff:127.0.0.1 if you are using IPv6.

You can now check the number of consumed points (number of failed logins) of the limiterSlowBruteByIP rate limiter for the IP that tried to log in.



yourRedisLabsEndpoint> GET login_fail_ip_per_day:::1
"1"

Failed login with an account that does exist

Now try log in with an existing account and use the wrong password. Then view all of the keys in your Redis database.



yourRedisLabsEndpoint> SCAN 0
1)"0"
2) "login_fail_ip_per_day:::1"
3) "login_fail_consecutive_username_and_ip:realuser@example.com_::1"

You can now check the number of points consumed for the IP that tried to log in for the limiterSlowBruteByIP rate limiter key.



yourRedisLabsEndpoint> GET login_fail_ip_per_day:::1
"2"

Check the number of consumed points for the limiterConsecutiveFailsByEmailAndIP rate limiter key.



yourRedisLabsEndpoint> GET login_fail_consecutive_username_and_ip:realuser@example.com_::1
"1"

Try logging in more than 3 times within 1 minute. After this, you will get this message displayed in your browser:

Too many requests. Retry after 60 seconds.

The login route for the given IP and username pair will be blocked for 60 seconds. This is because the blockDuration that we set for the limiterConsecutiveFailsByEmailAndIP rate limiter is 60 seconds. After 60 seconds, check the number of consumed points for the key again:



yourRedisLabsEndpoint> GET login_fail_ip_per_day:::1
(nil)

It does not exist anymore as we set the duration property to 60. The key is deleted after 60 seconds.

Now try login using an existing account with the wrong password. After this, log in with the correct password. This will delete the limiterConsecutiveFailsByEmailAndIP rate limiter key for the given user and IP pair. This occurs once the login is successful, as can be seen in the rate limit controller:



      ... 

        if (resEmailAndIP !== null && resEmailAndIP.consumedPoints > 0) {
          // Reset on successful authorisation
          await limiterConsecutiveFailsByEmailAndIP.delete(emailIPkey);
        }
      ...

You can do more thorough testing of POST requests using services such as Postman, which is a tool used to build and test APIs.

Conclusion

This is a basic example of how to rate limit a login route in an Express app using node-rate-limiter-flexible and Redis. node-rate-limiter-flexible was used to count and limit the number of login attempts by key. Redis was used to store the keys. We created a rate limiter middleware in an existing application with a login route and authentication. Two rate limiters were created. The first rate limiter rate-limited based on IP. The second rate-limited based on IP and the user's email address. Redis Labs was set up to create an online instance of Redis. The Redis Labs instance was connected to the Express app using an endpoint URL. Redis was installed locally and was connected to the online instance of Redis. Rate-limiting was tested by viewing the database keys, using the redis-cli, after attempted logins.

Here are some useful links for further study:

1) Redis Crash Course Tutorial - Learn the basics of Redis

2) Redis Caching in Node.js - Learn how to cache API calls using Redis.

3) API Rate Limiting with Node and Redis

4) node-rate-limiter-flexible: rate-limiting examples

5) Redis documentation

6) Redis Labs documentation

7) Redis Labs YouTube channel