DEV Community: Farai Bvuma

Setup Tailwind CSS v4.0 with Vite + React

Farai Bvuma — Thu, 25 Sep 2025 23:49:03 +0000

Introduction

I recently ran into some trouble trying to setup Tailwind CSS v4.0 with a new Vite + React project. If you are stuck trying to figure out how to proceed, here is a quick step-by-step guide to help you.

Configuration

In the project directory, run the following command to install tailwind.

npm install tailwindcss @tailwindcss/vite

Update your vite.config.ts file, importing tailwind and adding it as a plugin.

import { defineConfig } from "vite";
import react from "@vitejs/plugin-react";
import tailwindcss from "@tailwindcss/vite";

export default defineConfig({
  plugins: [react(), tailwindcss()],
});

Add the tailwind import to your global css file, in my case it was my src/index.css.

@import "tailwindcss";

Now go ahead and test your setup, this can be done in the App.tsx.

      <div className="text-3xl font-bold underline bg-red-700">
        Hello World!
      </div>

Conclusion

I hope this guide will help you with your setup, feel free to reach out if you have any questions.

Dynamic Styling with Props in Styled-Components

Farai Bvuma — Tue, 15 Jul 2025 02:08:33 +0000

Introduction

Have you ever been stuck trying to figure out how to manipulate the styles of a prop in React using styled-components? What about when you want to directly apply CSS rules based on a prop's value, even if that prop is not a standard CSS property? Here is a quick guide on how you can get this done.

Let's say that you have a button component with a prop called state(isLoading, isActive etc), and you want to change how this React component is displayed based on whether the state is true or false. Simply follow the below example, swapping out the CSS rules that you wish to conditionally apply. We are using TypeScript and styled-components in the below example.

const StyledComponent = styled.button<{ state?: boolean }>`
   // The base CSS styles for the button go here
   background-color: blue;

   // Styles will be conditionally applied based on the 'state' prop
   ${({ state }) => state && `
    // These CSS rules will apply only when the 'state' prop is true
    border: 1px solid darkblue;
    opacity: 0.8;
  `}
`;

How it works

Since state is not a CSS property(like color or padding), we use a JavaScript template literal( ${} ) to inject our custom logic directly into the CSS.

Inside the template literal, we provide a callback function(({ state }) => ... ) that is used by styled-components to pass the component's props. We have also used object destructuring( {state} ) to easily access the prop's value.

As previously mentioned, the aim is to conditionally render the button based on the state prop, and we do this by using the logical AND operator( && ), where if the state prop is truthy, the expression evaluates to the CSS string inside of the inner backticks, with styled-components proceeding to apply the CSS. Otherwise, if the state prop is falsy, no CSS is injected from the block.

Conclusion

Using this pattern to conditionally render components in React based on values of props is a great way to create dynamic components. Be sure to give it a try.

Build Apps with Google AI Studio: Anime Greetings Cards

Farai Bvuma — Sat, 05 Jul 2025 01:46:54 +0000

This post is my submission for DEV Education Track: Build Apps with Google AI Studio.

What I Built

I set out to build anime inspired AI generated greetings cards. This is the prompt that I used:

Please create an app that generates cute and unique greetings cards, using Imagen for anime inspired visuals, and Gemini for heartfelt messages. I will need to be able to export the finished app to run locally with minimal setup and then host it on Vercel.

Demo

Here is a link of the version I deployed to Vercel because I do not have a billed account. Here is the repo on GitHub.

My Experience

Getting this app up and running took way more time than advertised. On my first attempt, I couldn't get the app to render in the Google AI Studio's preview tab. After a little back and forth with the AI agent, I got it to work. Following the tutorial I tried to get it to deploy to cloudrun, only to hit a major roadblock because I do not have billing activated on my Google Cloud account. This was rather frustrating, so together with the AI agent we came up with a workaround, deploy to Vercel! Unbeknownst to me at the time, this would bring its own set of problems, mainly that the code used to build in the Google Studio does not immediately work when run locally, nor does it deploy in Vercel. I tried to work out a solution with the AI Agent only for it to completely stop working.

This is a really cool concept so I decided to give it another go, scrapping the original app and creating a new app with a new prompt. This time it worked right off the bat. I had to direct the agent to fix an issue with the greetings messages, where the app was displaying three messages instead of one. Since I have a bad habit of doing things the hard way, I decided to try running the app locally and deploying to Vercel. Unfortunately the agent was of no real help when it came to this. The agent became fixated on the importmap script, which is necessary to render the app in the preview tab of Google AI Studio, but not necessary for local builds and Vercel deployment. I discovered that the AI agent has a stubborn streak, even after being told numerous times to ignore the "issue", it repeatedly came back to it. It was an endless loop where it would analyse its own code, recognise that importmap in unnecessary for local builds, suggest deletion of the script, run the suggested upgrade only for it to automatically add the script again and then suggest its removal. Because of this it wasn't of much help when it came to running the app locally, even less so for deploying on Vercel. Thanks to my professional experience and help from another LLM, I was able to figure it out.

You would think this would be the end of it but unfortunately I ran into one more issue when deploying to Vercel, Imagen does not generate images unless the Gemini API Key is connected to a billed account, and a little bit of research shows that this can get quite expensive.

So what did I learn? Google's AI Studio is a really cool tool with potential to get your app ideas off the ground in record time, but pray that you do not need any fine tweaking. If it wasn't for my experience as a software developer I probably wouldn't have noticed some of the issues, and I definitely would not have been able to fix most of them. The initial app is serviceable, but after all this effort I'm too drained to ask it to fine tweak the presentation.

GitHub Issue Importer

Farai Bvuma — Fri, 30 May 2025 15:40:16 +0000

Did you know that GitHub does not offer a way to import multiple issues at once? I came across this problem whilst laying out my plans for a new project. I had created a number of tasks and I wanted to add these tasks as issues to my project in GitHub. Faced with the daunting task of manually adding all of these tasks as issues, I decided to peruse the web for an easy solution but came up empty handed. Since I had some free time, I decided to try developing a tool that will do all of this for me.

If you would like to import a number of issues in one go, all you need to do is create a CSV file with the issues in the following format:

title,body,labels
"Issue Title","Issue Description","Labels"

This is what such a file might look like:

title,body,labels
"Add dark mode","Implement dark mode toggle","feature,UI"

If you don't already have one, next you need to create a personal access token on GitHub. This can be done by accessing the developer settings in your GitHub profile.

Finally, clone the repo and follow the instructions.

Hopefully this will save you time if you ever wish to import multiple tasks automatically.

GitHub Issue Importer

Farai Bvuma — Sun, 30 Mar 2025 04:00:55 +0000

If you would like to import a number of issues in one go, all you need to do is create a CSV file with the issues in the following format:

title,body,labels
"Issue Title","Issue Description","Labels"

This is what such a file might look like:

title,body,labels
"Add dark mode","Implement dark mode toggle","feature,UI"

If you don't already have one, next you need to create a personal access token on GitHub. This can be done by accessing the developer settings in your GitHub profile.

Finally, clone the repo and follow the instructions.

Hopefully this will save you time if you ever wish to import multiple tasks automatically.

Data Structures and Algorithms: Dijkstra's Algorithm

Farai Bvuma — Fri, 20 Sep 2024 01:01:13 +0000

Introduction

Dijkstra's Algorithm is a greedy algorithm that is used to find the shortest path from a source vertex to all of the other vertices on a weighted directed graph. Being a greedy algorithm, an attempt is made to find the optimal solution by breaking the problem up into steps and solving these steps one at a time. The optimal solution in this case is the next vertex with shortest path. It is important to note that this algorithm cannot be used in a graph with negative weights.

Dijkstra's Algorithm Walkthrough

The algorithm starts by initialising the starting vertex of the graph with a distance of zero and all other vertices with distances of infinity. At this point all of the vertices are marked as unvisited. The algorithm will also initialise a priority queue to keep track of the vertices with the shortest known distances. The starting vertex is then dequeued(as it has a distance of zero) and is marked as visited. The algorithm will now check the edges of the adjacent vertices, calculating a new potential distance to each vertex by adding the weight to the distance from the current vertex. If the new distance is smaller than the currently known distance to the vertex, this distance is updated and the vertex is enqueued. The algorithm will then go on to select the next vertex from the priority queue(i.e. the vertex with the smallest distance), mark it as visited and will repeat the process until all of the vertices in the graph have been visited. We can illustrate this using the following graph:

Starting at vertex A with a distance of zero, the distances from A to all of the remaining vertices will be set as infinity. A is then added to a priority queue, before being dequeued, marked as visited and checking the distances to vertices B and D. As these distances are less than infinity, their calculated distances are updated as 2 and 6 respectively. Both vertices are then added to the priority queue.

As B has the shortest distance, it will be the next vertex to be dequeued, marked as visited and processed by the algorithm. The algorithm now checks B's adjacent vertices(D and C) and checks their distances from the starting node, A -> B -> C(2 + 3 = 5) and A -> B -> D(2 + 7 = 9). The algorithm then compares these newly calculated distances to the previously stored distances. The distance to C is updated to 5 and the distance to D remains unchanged at 6. C is now also added to the priority queue.

The shortest distance is now 5 so the vertex C is dequeued and marked as visited. It only has E as an adjacent vertex, with a distance of 2 + 3 + 5 = 10(A -> B -> C -> E). The vertex E is also added to the priority queue.

D is the next vertex to be dequeued and marked as visited since it has a distance of 6(A -> D). The algorithm will now check D's adjacent vertices. Vertex C has already been visited so no further action will be taken. Finally the algorithm will finish by dequeuing E and processing it.

Implementing Dijkstra's Algorithm in JavaScript

To implement Dijkstra's Algorithm in JavaScript, we can start off by creating a PriorityQueue class.

class PriorityQueue {
  constructor() {
    this.elements = [];
  }

  enqueue(node, weight) {
    this.elements.push({ node, weight });
    this.elements.sort((a, b) => a.weight - b.weight);
  }

  dequeue() {
    return this.elements.shift(); 
  }

  isEmpty() {
    return this.elements.length === 0;
  }
}

Along with the constructor, we will create an enqueue() method to add a vertex and its weight to the priority queue. These vertices are then sorted according to their weights, that is to say, the vertex with the smallest weight(or distance) will come first. The dequeue() method is used to return the vertex with the smallest weight from the priority queue and the isEmpty() method is used to check if the priority queue has any vertices.

Next we will create a Graph class which will have a constructor. This constructor will use an object to store an adjacency list.

  constructor() {
    this.adjacencyList = {}; 
  }

The Graph class will also have the addNode() method which will be used to add a vertex and the addEdge() method which will be used to add edges to a vertex.

  addNode(node) {
    this.adjacencyList[node] = [];
  }

  addEdge(node1, node2, weight) {
    this.adjacencyList[node1].push({ node: node2, weight });
  }

The addNode() method will initialize an empty array for the adjacency list for a given vertex. This array will then go on to store all of the edges for the node provided in the addEdge() method. For example, to add nodes A and B from our graph, we will use:

graph.addNode('A');
graph.addNode('B');

The adjacency lists for the two nodes will look like this:

{
  A: [],
  B: []
}

And then the edge can be added as follows

graph.addEdge('A', 'B', 2);

This results in the adjacency list looking like this:

{
  A: [{ node: 'B', weight: 2 }],
}

We will also need to create the dijkstra() method to run the algorithm:

dijkstra(start) {
    const distances = {};
    const previous = {};
    const pQueue = new PriorityQueue();

    for (const node in this.adjacencyList) {
      distances[node] = Infinity;
      previous[node] = null;
    }

    distances[start] = 0;
    pQueue.enqueue(start, 0);

    while (!pQueue.isEmpty()) {
      const { node: currentNode } = pQueue.dequeue();

      for (const neighbor of this.adjacencyList[currentNode]) {
        const { node: adjacent, weight } = neighbor;
        const newDist = distances[currentNode] + weight;

        if (newDist < distances[adjacent]) {
          distances[adjacent] = newDist;
          previous[adjacent] = currentNode;
          pQueue.enqueue(adjacent, newDist); 
        }
      }
    }

   return { distances, previous };
  }

This method will have a distances object to map the calculated distances from the starting vertex to all of the remaining vertices in the graph, a previous object to keep track of each vertex's previous vertex and a priority queue which will be used to keep track of the vertices with the shortest distances. These will be initialised and the distances from the starting vertex will be calculated, before returning the distances and previous objects.

Lastly we will create the getShortestPath() method, which will be used to return the shortest path between two vertices.

 getShortestPath(start, end) {
    const { distances, previous } = this.dijkstra(start);
    const path = [];
    let currentNode = end;

    while (currentNode !== null) {
      path.push(currentNode);
      currentNode = previous[currentNode];
    }

    return {
      distance: distances[end],
      path: path.reverse(),
    };
  }

Conclusion

This article explains the logic behind Dijkstra's Algorithm to find the shortest path in a graph. This article also shows how the algorithm can be implemented in JavaScript using a priority queue, although this could be done more efficiently using a min-heap. Some real world applications of Dijkstra's Algorithm include GPS and mapping software(Google Maps), route optimization in public transport systems, finding the most efficient route for sending data packets in internet routing protocols and AI pathfinding in video games.

Data Structures and Algorithms: Graphs

Farai Bvuma — Thu, 05 Sep 2024 03:05:57 +0000

Introduction

A graph is a data structure with a number of vertices(nodes) and edges(connections) between them.

A tree is an example of a graph. Every tree is a graph but not every graph is a tree, for example, graphs that have cycles are not trees. A tree will have one root and one unique path between two nodes whilst a graph can have many roots and multiple paths between vertices.

Basic Terminology

Vertex: A node in a graph.

Edge: The connection between two vertices.

Directed: When the connection between two vertices has a direction. This implies that there is only one way to get from one vertex to another. An example could be graph showing the cities(vertices) and the routes(edges) between them.

Undirected: When the connection between two vertices on a graph goes both ways. An example could be a graph showing people(vertices) connected by their friendships.

Degree: The number of edges connected to a vertex. The vertices of a directed graph can have an indegree or an outdegree, which is the number of edges pointing towards and away from the vertex respectively.

Weighted: A graph in which the edges have values as weights. An example could be a road map, where the distances between nodes are represented as weights.

Cyclic: A graph that has a path from at least one vertex back to itself.

Acyclic: A graph that has no cycles, that is to say, no node has a path back to itself. A Directed Acyclic Graph is a type of graph that can be used to show data processing flows.

Dense: When a graph has close to the maximum possible number of edges

Sparse: When a graph has close to the minimum possible number of edges.

Self-loop: When an edge has one vertex linking to itself.

Multi-edge: When a graph has multiple edges between two vertices.

Simple: When a graph has no self-loops nor multi-edges.

To get the maximum number of edges in a simple directed graph: n*(n-1) where n is the number of nodes.

To get the maximum number of edges in a simple undirected graph: n*(n-1)/2 where n is the number of nodes.

Implementing graphs in JavaScript

To implement a graph, we can start by specifying the vertices and edges of a graph, below is an example of how to do this given the following graph:

const vertices = ["A", "B", "C", "D", "E"];

const edges = [
  ["A", "B"],
  ["A", "D"],
  ["B", "D"],
  ["B", "E"],
  ["C", "D"],
  ["D", "E"],
];

Then we can create a function to find what is adjacent to a given vertex:

const findAdjacentNodes = function (node) {
  const adjacentNodes = [];
  for (let edge of edges) {
    const nodeIndex = edge.indexOf(node);
    if (nodeIndex > -1) {
      let adjacentNode = nodeIndex === 0 ? edge[1] : edge[0];
      adjacentNodes.push(adjacentNode);
    }
  }
  return adjacentNodes;
};

And another function to check if two vertices are connected:

const isConnected = function (node1, node2) {
  const adjacentNodes = new Set(findAdjacentNodes(node1));
  return adjacentNodes.has(node2);
};

Adjacency List

An adjacency list is a representation of a graph where all of the vertices that are connected to a node are stored as a list. Below is a graph and a visual representation of its corresponding adjacency list.

An adjacency list can be implemented in JavaScript by creating two classes, a Node class and a Graph class. The Node class will consist of a constructor and a connect() method to join two vertices. It will also have the isConnected() and getAdjacentNodes() methods which work in exactly the same manner as shown above.

class Node {
  constructor(value) {
    this.value = value;
    this.edgesList = [];
  }
  connect(node) {
    this.edgesList.push(node);
    node.edgesList.push(this);
  }
  getAdjNodes() {
    return this.edgesList.map((edge) => edge.value);
  }
  isConnected(node) {
    return this.edgesList.map((edge) => 
    edge.value).indexOf(node.value) > -1;
  }
}

The Graph class consists of a constructor and the addToGraph() method which adds a new vertex to the graph.

class Graph {
  constructor(nodes) {
    this.nodes = [...nodes];
  }
  addToGraph(node) {
    this.nodes.push(node);
  }
}

Adjacency Matrix

A 2-D array where each array represents a vertex and each index represents a possible connection between vertices. An adjacency matrix is filled with 0s and 1s, with 1 representing a connection. The value at adjacencyMatrix[node1][node2] will show whether or not there is a connection between the two specified vertices. Below is is a graph and its visual representation as an adjacency matrix.

To implement this adjacency matrix in JavaScript, we start by creating two classes, the first being the Node class:

class Node {
  constructor(value) {
    this.value = value;
  }
}

We then create the Graph class which will contain the constructor for creating the 2-D array initialized with zeros.

class Graph {
  constructor(nodes) {
    this.nodes = [...nodes];
    this.adjacencyMatrix = Array.from({ length: nodes.length },   
    () => Array(nodes.length).fill(0));
   }
}

We will then add the addNode() method which will be used to add new vertices to the graph.

  addNode(node) {
    this.nodes.push(node);
    this.adjacencyMatrix.forEach((row) => row.push(0));
    this.adjacencyMatrix.push(new Array(this.nodes.length).fill(0));
  }

Next is the connect() method which will add an edge between two vertices.

  connect(node1, node2) {
    const index1 = this.nodes.indexOf(node1);
    const index2 = this.nodes.indexOf(node2);

    if (index1 > -1 && index2 > -1) {
      this.adjacencyMatrix[index1][index2] = 1;
      this.adjacencyMatrix[index2][index1] = 1; 
    }
  }

We will also create the isConnected() method which can be used to check if two vertices are connected.

  isConnected(node1, node2) {
    const index1 = this.nodes.indexOf(node1);
    const index2 = this.nodes.indexOf(node2);

    if (index1 > -1 && index2 > -1) {
      return this.adjacencyMatrix[index1][index2] === 1;
    }
    return false;
  }

Lastly we will add the printAdjacencyMatrix() method to the Graph class.

  printAdjacencyMatrix() {
    console.log(this.adjacencyMatrix);
  }

Breadth First Search

Similar to a Breadth First Search in a tree, the vertices adjacent to the current vertex are visited before visiting any subsequent children. A queue is the data structure of choice when performing a Breadth First Search on a graph.

Below is a graph of international airports and their connections and we will use a Breadth First Search to find the shortest route(path) between two airports(vertices).

In order to implement this search algorithm in JavaScript, we will use the same Node and Graph classes we implemented the adjacency list above. We will create a breadthFirstTraversal() method and add it to the Graph class in order to traverse between two given vertices. This method will have the visitedNodes object, which will be used to store the visited vertices and their predecessors. It is initiated as null to show that the first vertex in our search has no predecessors.

breathFirstTraversal(start, end) {
    const queue = [start];
    const visitedNodes = {};
    visitedNodes[start.value] = null;

    while (queue.length > 0) {
      const node = queue.shift();

      if (node.value === end.value) {
        return this.reconstructedPath(visitedNodes, end);
      }
      for (const adjacency of node.edgesList) {
        if (!visitedNodes.hasOwnProperty(adjacency.value)) {
          visitedNodes[adjacency.value] = node;
          queue.push(adjacency);
        }
      }
    }
  }

Once the end vertex is found, we will use the reconstructedPath() method in the Graph class in order to return the shortest path between two vertices. Each vertex is added iteratively to the shortestPath array, which in turn must be reversed in order to come up with the correct order for the shortest path.

reconstructedPath(visitedNodes, endNode) {
    let currNode = endNode;

    const shortestPath = [];

    while (currNode !== null) {
      shortestPath.push(currNode.value);
      currNode = visitedNodes[currNode.value];
    }
    return shortestPath.reverse();
  }

In the case of the graph of international airports, breathFirstTraversal(JHB, LOS) will return JHB -> LUA -> LOS as the shortest path. In the case of a weighted graph, we would use Dijkstra's algorithm to find the shortest path.

Depth First Search

Similar to a depth first search in a tree, this algorithm will fully explore every descendant of a vertex, before backtracking to the root. A stack is the data structure of choice for depth first traversals in a graph.

A depth first search can be used to detect a cycle in a graph. We will use the same graph of international airports to illustrate this in JavaScript.

Similar to the Breadth First Search algorithm above, this implementation of a Depth First Search algorithm in JavaScript will use the previously created Node and Graph classes. We will create a helper function called depthFirstTraversal() and add it to the Graph class.

  depthFirstTraversal(start, visitedNodes = {}, parent = null) {
    visitedNodes[start.value] = true;

    for (const adjacency of start.edgesList) {
      if (!visitedNodes[adjacency.value]) {
        if (this.depthFirstTraversal(adjacency, visitedNodes, start)) {
          return true;
        }
      } else if (adjacency !== parent) {
        return true;
      }
    }

    return false;
  }

This will perform the Depth First Traversal of the graph, using the parent parameter to keep track of the previous vertex and prevent the detection of a cycle when revisiting the parent vertex. Visited vertices will be marked as true in the visitedNodes object. This method will then use recursion to visit previously unvisited vertices. If the vertex has already been visited, we check it against the parent parameter. A cycle has been found if the vertex has already been visited and it is not the parent.

We will also create the wrapper function hasCycle() in the Graph class. This function is used to detect a cycle in a disconnected graph. It will initialize the visitedNodes object and loop through all of the vertices in the graph.

hasCycle() {
    const visitedNodes = {};

    for (const node of this.nodes) {
      if (!visitedNodes[node.value]) {
        if (this.depthFirstTraversal(node, visitedNodes)) {
          return true;
        }
      }
    }
    return false;
  }

In the case of the graph of international airports, the code will return true.

Depth First Traversal of a graph is also useful for pathfinding(not necessarily shortest path) and for solving mazes.

Conclusion

A firm understanding of graphs as a data structure and of their associated algorithms is absolutely necessary when furthering one's studies of data structures and algorithms. Although not as beginner friendly as the previous posts in this series, this guide should prove useful to deepen your understanding of data structures and algorithms.

Data Structures and Algorithms: Breadth First Search

Farai Bvuma — Wed, 22 May 2024 01:28:58 +0000

Introduction

In a breadth first search, we traverse a tree one level at a time, visiting each node on a level before visiting any potential children nodes. We will use a queue to explore this data structure. See part three of this series for further details on queues.

Breadth First Traversal

Considering the root of the tree, we add the root to the queue. We then remove the node at the front of the queue and print out its value. We also consider any children the node might have and then add them to the back of the queue, going from left to right. We repeat this process until the queue is empty. We can use the following binary tree to illustrate this.

In this example we start by adding the root to our queue.

[a]

We remove the node at the front of the queue, printing out its value. We then add any children that this node might have to the back of the queue.

[b, c]

We repeat the process, removing the node at the front of the queue and printing its value, and then we add any of its children to the back of the queue.

[c, d, e]

We continue the process until the queue is empty. The resulting breadth first traversal of our example tree will be: a, b, c, d, e, f, g.

A breadth first traversal can be achieved in javascript using the following code:

const breathFirstTraversal = (root) => {
  let queue = [root];

  while (queue.length > 0) {
    let currentNode = queue.shift();

    console.log(currentNode.val);

    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }
    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }
  }
};

Breadth First Search

Knowing how to implement a breadth first traversal, we can now proceed to implement a breadth first search in order to find a target value in a tree. Here is how this can be done in javascript:

const breathFirstSearch = (root, target) => {
  let queue = [root];

  while (queue.length > 0) {
    let currentNode = queue.shift();

    if (currentNode.val === target) {
      return true;
    }

    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }
    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }
  }

  return false;
};

A breadth first traversal can also be used to add up all of the node values in a tree.

Conclusion

This concludes the basics of a breadth first traversal and how this can be used as a basis for a breadth first search. As previously stated, the implicit data structure used in a breadth first traversal is a queue.

Data Structures and Algorithms: Depth First Search

Farai Bvuma — Fri, 03 May 2024 03:39:39 +0000

Introduction

In Depth First Search(DFS), we use an algorithm to traverse data structures such as trees and graphs. Starting with the root node, we traverse as deeply as possible on a branch(arriving at a leaf) before backtracking to a parent node and visiting its other children nodes. In code, this can either be done iteratively or recursively.

Types of Traversal

Traversal is the process by which we can visit each and every node within in a tree. I will use the following tree to demonstrate the 3 types of traversal in a DFS.

1. Pre-order

In a pre-order traversal, we print out the value of the parent node before printing out the values of the children nodes. Here is some pseudocode showing the process.

visitNode() 
recurseLeft()
recurseRight()

Here is some code showing how pre-order traversal can be achieved iteratively using a stack.

const preOrderTraversal = (root) => {
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node.val);
    if (node.right !== null) {
      stack.push(node.right);
    }
    if (node.left !== null) {
      stack.push(node.left);
    }
  }
};

The current node is pushed onto the stack and its value is printed out. If the current node has children, they are pushed onto the stack, starting with the right child followed by the left child.

Alternatively, the same result can be achieved recursively. A good base case will be when the tree is empty, that is to say, when it has no leaves. This can be done as follows:

const preOrderTraversal = (root) => {
  if (root === null) {
    return;
  }

  console.log(root.val);
  preOrderTraversal(root.left);
  preOrderTraversal(root.right);
};

Using the above binary tree as an example, the result of a pre-order traversal will be: 4, 21, 5, 8, 7, 13, 2.

It is worth noting that the root will always be at the beginning of a pre-order traversal.

2. In-order

In the case of an in-order traversal, we start at root and go left as deep into the tree as possible. When we reach a leaf(a node with no children), we print its value, print the value of the parent and then the value of the right leaf. The process is then repeated up the tree. The following is the pseudocode:

recurseLeft()
visitNode() 
recurseRight()

As with the pre-order traversal, an in-order traversal can also be achieved iteratively:

const inOrderTraversal = (root) => {
  const tempStack = [];
  const inOrder = [];

  while (true) {
    if (root !== null) {
      tempStack.push(root);
      root = root.left;
    } else {
      if (tempStack.length === 0) break;

      root = tempStack.pop();
      inOrder.push(root.val);
      root = root.right;
    }
  }
  return console.log(inOrder);
};

An in-order traversal can also be achieved recursively:

const inOrderTraversal = (root) => {
  if (root === null) {
    return;
  }

  inOrderTraversal(root.left);
  console.log(root.val);
  inOrderTraversal(root.right);
};

Using the above binary tree as an example, the result of an in-order traversal will be: 5, 21, 8, 4, 13, 7, 2. It is interesting to note that the root will always be somewhere in the middle of an in-order traversal.

3. Post-order

As for a post-order traversal, we start at the root and go left until we reach a leaf. The value of this leaf is printed and then we go back up one and then go right, printing the value of the right leaf. Finally we go back up and print the value of the parent, before repeating the process up the tree. Here is the pseudocode:

recurseLeft()
recurseRight()
visitNode()

This is how a post-order traversal can be achieved iteratively utilizing a stack and an array:

const postOrderTraversal = (root) => {
  if (!root) return [];

  const tempStack = [root];
  const postOrder = [];

  while (tempStack.length) {
    const node = tempStack.pop();

    postOrder.unshift(node.val);

    if (node.left) {
      tempStack.push(node.left);
    }
    if (node.right) {
      tempStack.push(node.right);
    }
  }
  return console.log(postOrder);
};

Here we use the temporary stack,tempStack, to keep track of the nodes to be visited. In each iteration we remove a node from this temporary stack and add its value to the postOrder array. If children nodes exist, they are pushed onto the temporary stack.

Similar to the previous two types of traversal, a a post-order traversal can also be achieved recursively:

const postOrderTraversal = (root) => {
  if (root === null) {
    return;
  }

  postOrderTraversal(root.left);
  postOrderTraversal(root.right);
  console.log(root.val);
};

Using the above binary tree as an example, the result of a post-order traversal will be: 5, 8, 21, 13, 2, 7, 4.
It is also worth noting that the root will always be at the end of a post-order traversal. This is because we will visit and print the values of all of the children before printing out the value of the parent node.

Conclusion

This concludes the three types of traversal that can be used in a depth first search. The implicit data structure used here is a stack. A depth first search can be useful when you want to compare the shape and structure of two trees.

Data Structures and Algorithms: Trees

Farai Bvuma — Fri, 26 Apr 2024 00:14:30 +0000

Trees are a hierarchical data structure represented by nodes. Each node will have a value and possible children.

Terminology

Root - The first node in a tree.

Height - The length of the longest path from the root to the furthest child node.

Leaves - Nodes without children.

Binary Tree - A tree that has at most 2 children. Usually described as left or right.

General Tree - any tree with 0 or more children.

Binary Search Tree - a tree which has a specific ordering and at most 2 children nodes.

Balanced - a tree is considered to be balanced when the left and right children are of the same height.

Branching Factor - the amount of children that a tree has, for example, a binary tree has a branching factor of 2.

Traversal - The process by which each node in a tree is visited. The two main methods for tree traversal are Depth First Traversal and Breadth First Traversal.

Conclusion

The aim of this article was to serve as an introduction to trees. The next articles will go into detail about the types of tree traversal.

Data Structures and Algorithms: Quick Sort

Farai Bvuma — Wed, 13 Mar 2024 02:10:10 +0000

The quick sort is a divide and conquer algorithm. This algorithm can be used to quickly order any given array.

How it works

Given an array as input, we start by selecting an element of the array to act as the pivot.

We then walk through the array, comparing each element to the pivot. Elements that are less than the pivot are placed to the left whilst elements that are greater than than the pivot are placed to the right. This will result in a weakly sorted array after the first run through.

In order to further sort the array, we now select a pivot for the elements to the left and a separate pivot for the elements on the right.

We then proceed to repeat the process until we get to an empty array or an array with a single element.

The single element arrays are then concatenated into a new sorted array.

Below I will demonstrate how this can be applied in JavaScript using recursion.

1. Select pivot

There are many ways in which a pivot can be selected. Some prefer to use the first element in the array and others prefer to select an element from somewhere in the middle. As a personal preference I like to select the last element of the array.

  let pivot = array[array.length - 1];

2. Establish base case

Following the lead from the previous article, we will proceed to establish a base case for the recursive algorithm. When the array has only one element it will no longer need to call the function, as this single element array is already sorted.

 if (array.length <= 1) {
    return array;
  }

3. Split

Now we will split our array into two separate subarrays. All elements of the array found to have values smaller than the pivot will be put into one subarray, and all elements found to have values greater than the pivot will be put into another subarray.

  let low = [];
  let high = [];

  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      low.push(array[i]);
    } else {
      high.push(array[i]);
    }
  }

4. Establish recursive case

Lastly, we need to provide the recursive case for the function. Here the quick sort function will be called on the two separate subarrays until they reach the base case, at which point they will be concatenated with the pivot to return a sorted array.

return [...QuickSort(low), pivot, ...QuickSort(high)];

Here we use the spread operator(...) to merge the elements of the subarrays into the sorted array.

Here is the complete code for the algorithm.

function QuickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  let pivot = array[array.length - 1];
  let low = [];
  let high = [];

  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      low.push(array[i]);
    } else {
      high.push(array[i]);
    }
  }
  return [...QuickSort(low), pivot, ...QuickSort(high)];
}

Conclusion

This concludes the basics of the quick sort algorithm. It is an incredibly popular algorithm, mainly due to its relative speed and its simplicity, with the added advantage of not needing extra memory. It is a great choice when one wants to search a dataset for information.

Data Structures and Algorithms: Recursion

Farai Bvuma — Fri, 02 Feb 2024 02:30:15 +0000

Introduction

Recursion is a programming technique where a function calls itself repeatedly until it reaches a base case, which is the point at which the problem is solved.

There are two steps to recursion:

Base case
Recursive case

Solving a problem with recursion

We can use recursion to solve the problem of finding the factorial of any given integer.

Base Case

To solve this with recursion, first we must create our base case. We will use the base case to prevent the function from running forever, at which point it will stop calling itself to return a result.

Given that the factorial of a number n is the product of all positive integers less than or equal to n, the function will stop calling itself once n is equal to 1. At this point the return value will be 1.

if(n === 1) {
   return 1;
}

Recursive Case

The second part is recursive case, where the function will call itself until it reaches the base case.
In order to find the factorial, the function will be call itself whilst decrementing the value of n.

n * factorial(n - 1);

The recursive case can be divided into 3 steps:

Pre: where an operation is performed before recursing, for example, multiplying the function by n.
Recursion: where the function is called.
Post: where n operation is performed after recursing, for example, logging the value of n.

With the base case and recursive case defined, we can now write out the function to find the factorial of an integer.

function factorial(n){
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Conclusion

Recursion can be a useful tool for breaking down complex programming problems. It is often used as an alternative to iteration(for and while loops) and is very useful for traversing trees and graphs.