Never Get React Recursion Wrong Again

Recently I came upon an interesting problem. I wanted to create my blog using Notion as the CMS.

Markdown Remark and MDX are great tools for using existing components in markdown files, but Notion has no knowledge of my files.

This created an issue of being unable to use my existing styled-components. So how do I connect my components to the markdown?

This article will be covering how to use recursion alongside a Factory component to convert a tree of data into React elements.

If you're curious about recursion, component factories, or custom hooks you might find something you can use here. Hopefully! 😃

Breaking down the problem

We'll skip the details of how exactly data gets to the front end. A lot of tree traversal problems follow this pattern so don't get too focused on the way my particular structure may differ from yours.

That being said let's look at the structure that became my muse.

{
  "type": "root",
  "children": [
    {
      "type": "element",
      "tagName": "p",
      "properties": {},
      "children": [
        {
          "type": "text",
          "value": "Recently I came upon an interesting problem. I wanted to create my blog using "
        },
        {
          "type": "element",
          "tagName": "a",
          "properties": {
            "href": "https://www.notion.so/product"
          },
          "children": [
            {
              "type": "text",
              "value": "Notion"
            }
          ]
        },
        {
          "type": "text",
          "value": " as the CMS."
        }
      ]
    },
    ...
  ]
}

The goal was to take this structure, traverse it, and have each node rendered as a React element with proper nesting of its children. Let's break down the problem into each of its components.

Input

A tree of nodes with the following properties:

type - a string declaring the type of node
children - an array of nodes
tagName - a string representing the HTML tag of the element
properties - an object of HTML attributes related to the element
value - a string of text to be rendered

Problem description

Given a tree of nodes, return React elements with the same hierarchy.

Output

React elements with attributes appropriate to the HTML tag and children correctly allocated in parent elements.

Examining the solution

To solve the problem I ended up using two pieces a Factory component and useNotionElement custom hook.

The final solution manages to create the needed product in one pass.

Giving us O(n) memory efficiency and time complexity, because we visit each node once and only once.

Factory

Based on the factory pattern, the Factory component is mostly what it sounds like. It pumps out components depending on the input.

It accepts the blocks prop—a single node of our tree.

const Factory = ({ blocks }) => {
  const element = useNotionElement(blocks);
  const { value, children, tagName } = element;

  // Delete properties that shouldn't be spread into element as attributes
  delete element.tagName;
  delete element.type;
  delete element.value;

  switch (tagName) {
    case "h2":
      return <PrimaryHeading {...element} />;
	...
    case "root":
      return <>{children}</>;

    default:
      return "";
  }
};

In the first few lines, we assign the element variable to hold the result of useNotionElement and destructure some properties for later use.

Then we delete any property that isn't valid attributes on HTML elements.

Finally, the switch statement decides which component to render based on tagName and we spread the element to the component.

The Factory component produces an element for every node—any unsupported or unaccounted cases are handled by producing an empty string.

Handling data with a custom hook

useNotionElement houses logic used to manipulate the data as needed. Such as adding href attributes to link elements.

Its input is the node that was passed into the Factory component's block prop.

Note that we are still working within that components closure!

It returns the processed element-to-be data as an object.

This hook allows us to maintain separation of concerns and helps by allowing us to be more declarative, making it easy to add data-altering functions—like handleProperties--in the future.

const useNotionElement = blocks => {
  let children;

  if (blocks.type !== "text") {
    children = generateChildren(blocks);
  }
    
  const tagName = getTag(blocks);
  const properties = handleProperties(blocks);

  return {
    ...blocks, // spread all existing block properties
    ...properties, // spread updated properties
    tagName, // overwrite existing blocks.tagName
    children // overwrite existing blocks.children
  };
};

Our focus is how this hook is a part of a recursive solution!

How is exactly is recursion working here?

The generateChildren function is where the magic happens! A single, but powerful line of code.

So we've looked at the code, now let's follow the data. Here's how it works!

To begin with, the data we source from Notion is given to the Factory component through the blocks prop.

Upon arriving inside Factory we give blocks immediately to useNotionElement where we hit an if statement.

The condition blocks.type !== "text" makes sure we only perform the next bit of work on nodes we know have a children property.

When we find children we call generateChildren which will give each child into a new Factory component.

Here the process begins again so let's pause and take in what that means.

At this point of the code, the current node we're working on isn't even close to becoming a React element yet. Our useNotionElement function hasn't even finished yet!

This algorithm digs deeper into our tree before completing work on a given node.

Meaning that the lower-level (deeply nested) nodes will be processed first.

Depth First Traversal

For those interested—this is in fact post-order traversal because we process the leaf nodes first.

If you're not familiar, don't feel bad I was not either and this algorithm took me a lot of work.

If you have time, check out the bookmarked section of this video and this article if you'd like to start digging down the rabbit hole.

If you do keep in mind the problem we're working on is not a binary tree. Where the children property on our structure would be replaced by left and right properties.

In our problem, we are not searching for a specific value. We are gathering information about each node as we traverse to then use that information to create what we need.

The important part is that our data structure is recursively defined.

Meaning if we pick any node in our tree it is just a smaller tree.

Put even more simply, the object we're working with is a big thing made of smaller things of the exact same type as the big thing.

It's this quality that allows for recursion and thus completing our work with only one pass of our data structure.

As long as our node has a children property the first child children[0] will be passed to Factory and recursion continues.

The recursion stops when we reach a node with a type of text. Which we know does not have children—a leaf node.

Let's say blocks.children only has one element—a text node. Calling generateChildren(blocks) will return an array containing a React fragment with that text node's value string.

This newly assigned children variable will eventually be spread as {...element} in Factory thus wrapping it within the appropriate parent element as work our way back up the tree.

Whew! That was a lot. Please feel free to take a break I'll wait up.

Wrapping up

Now that we've seen how it all works, let's do a quick recap.

First, we broke the problem down based on what was available and what we wanted:

Input
Problem description
Desired output

After that, we implemented some known patterns to help us organize and accomplish our mission.

Then, we dug into recursion and figured out exactly how it applied to our solution and end product.

One thing you may have noticed was the lack of an explicit base case for recursion. In this scenario, we were working with an implied base case—when a node is known to not have a children property, skip it.

Again, remember that none of this was exactly necessary. Using local markdown files and MDX would have been a very quick and easy solution.

My curiosity got the better of me and I dug into something I thought would be fun, so I figured I'd give this go.

Thanks for reading! 🙂

Hope this was able to help you in some way.