Table of contents

I wanted to display a list of all headings on my page. This is commonly known as a "table of contents". After looking around online, I found an algorithm that was able to generate a TOC (table of contents) from a list of headings. Although only up to two levels deep. So H1s and H2s.

Old algorithm

I don't remember where I got the idea from, but here is the code. It's more for completeness sake anyway.

function generateHeadingsTreeFrom(
    headingElements: HTMLHeadingElement[],
): Heading[] {
    const headings: Heading[] = [];

    for (const headingElement of headingElements) {
        const { innerText: text, id, nodeName } = headingElement;
        const heading: Heading = { children: [], id, text };

        if (nodeName === "H1") {
            headings.push(heading);
        } else if (nodeName === "H2" && headings.length > 0) {
            headings[headings.length - 1].children.push(heading);
        }
    }

    return headings;
}

Setup

I wanted to create an algorithm that can handle any depth. Let's go through my thought process on how to create this.

First, this is the code I use to get my heading elements:

const headings = Array.from(
    document.querySelectorAll("h1, h2, h3, h4, h5, h6"),
) as HTMLHeadingElement[]; // I'm using typescript btw :)

const tocTree = createTocTreeFrom(headings); // This is the function to implement.

TocTreeNode

Here is the TocTreeNode definition:

interface TocTreeNode {
    text: string;
    children: TocTreeNode[];
}

New "any depth" toc

function createTocTreeFrom(headings: HTMLHeadingElement[]): TocTreeNode[] {
    const nodes: TocTreeNode[] = [];

    for (const { tagName, innerText: text } of headings) {
        const matches = HEADING_TAG_REGEX.exec(tagName);

        if (!matches) {
            continue;
        }

        const headingLvl = parseInt(matches[1]);

        if (headingLvl !== 1) {
            continue;
        }

        nodes.push({ children: [], text });
    }

    return nodes;
}

The code above returns a simple list of all H1 elements. So let's step it up a notch. First, add an additional parameter desiredLvl, so what we look for can be customized.

function createTocTreeFrom(
    headings: HTMLHeadingElement[],
    desiredLvl: number,
): TocTreeNode[] {
    // ....

    if (headingLvl !== desiredLvl) {
        continue;
    }

    // ...
}

Let's add depth to it, by actually providing something for the children attribute. For now, let's just call the function recursively, but one level deeper, so desiredLvl + 1. We also want to not include previous elements, as otherwise, we would loop indefinitely.

function createTocTreeFrom(
    headings: HTMLHeadingElement[],
    desiredLvl: number,
): TocTreeNode[] {
    const nodes: TocTreeNode[] = [];

    for (let i = 0; i < headings.length; i++) {
        const { tagName, innerText: text } = headings[i];
        const matches = HEADING_TAG_REGEX.exec(tagName);

        if (!matches) {
            continue;
        }

        const headingLvl = parseInt(matches[1]);

        if (headingLvl !== desiredLvl) {
            continue;
        }

        const children = createTocTreeFrom(headings.slice(i + 1), desiredLvl + 1);

        nodes.push({ children, text });
    }

    return nodes;
}

But this algorithm is flawed. Consider the following headings:

<h1>1</h1>
<h2>1.1</h2>
<h1>2</h1>
<h2>2.1</h2>

The output would be:

- 1
  children:
    - 1.1
    - 2.1
- 2
  children:
    - 2.1

As you can see, the heading 2.1 is listed under the heading 1, which is quite incorrect. This happens because we never considered the hierarchy of the headings, and just added all smaller headings to the bigger ones.

Luckily, this is a relatively simple fix. Instead of just checking if the heading has the desired level and then adding it, we now also check if the heading is actually bigger than the current one. If it's bigger, all the next elements are of no concern to us, so we can simply return from the function.

This final algorithm is:

function createTocTreeFrom(
    headings: HTMLHeadingElement[],
    desiredLvl: number,
): TocTreeNode[] {
    const nodes: TocTreeNode[] = [];

    for (let i = 0; i < headings.length; i++) {
        const { tagName, innerText: text } = headings[i];
        const matches = HEADING_TAG_REGEX.exec(tagName);

        if (!matches) {
            continue;
        }

        const headingLvl = parseInt(matches[1]);
        const node: TocTreeNode = { children: [], text };

        if (headingLvl < desiredLvl) {
            return nodes;
        }

        if (headingLvl === desiredLvl) {
            node.children = createTocTreeFrom(headings.slice(i + 1), desiredLvl + 1);
            nodes.push(node);
        }
    }

    return nodes;
}

How to display the toc

Plain JavaScript / Typescript

function displayToc(entries: TocTreeNode[]): HTMLElement {
    const listElm = document.createElement("ul");
    listElm.style.marginLeft = "1em";

    for (const entry of entries) {
        const entryElm = document.createElement("li");
        entryElm.append(entry.text);

        if (entry.children.length > 0) {
            entryElm.appendChild(displayToc(entry.children));
        }

        listElm.appendChild(entryElm);
    }

    return listElm;
}

React

function TableOfContents({ nodes }: TableOfContentsProps): ReactElement {
    return (
        <ul style={{ marginLeft: "1em" }}>
            {nodes.map((node) => (
                <>
                    <li>{node.text}</li>
                    {node.children && <TableOfContents nodes={node.children} />}
                </>
            ))}
        </ul>
    );
}