Make Yer Own Binary Tree!

Sneak peek into the implementation behind this page.

The result of graphVizDOT is fed into graphviz-react

import {v4 as uuid} from 'uuid'

export default class BinaryTree {
    constructor(val, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
        // Create an id for use with DOT strings.
        // Otherwise we can only support unique values.
        // Having letters and hyphens in the ids seems to break graphViz.
        // This should be good enough for our purposes
        this.id = uuid().replace(/[-A-Za-z]/g, '')
    }

    get graphVizDOT() {
        // Returns a string that can be fed into graphviz-react
        // See https://graphs.grevian.org/ for basic intro to the syntax
        const res = `graph { ${this.makeDOTString()} }`
        return res
    }

    makeDOTString() {
        // Recursively create a DOT string for the node and all of its children
        let res = `${this.id}[label="${this.val}"];`
        for (let direction of ["left", "right"]) {
            const child = this[direction]
            if (child !== null) {
                res += `${this.id} -- ${child.id}`
                // If the node has no sibling, label the edge.
                // Otherwise image will not be clear if left or right.
                const hasNullSibling =
                    (direction === "left" && this.right === null)
                    || (direction === "right" && this.left === null)
                if (hasNullSibling) {
                    res += `[label="(${direction})"]`
                }
                res += ";"
                res += child.makeDOTString()
            }
        }
        return res
    }
}

BinaryTree.fromLevelOrder = function btFromLevelOrder(levelOrderTraversal) {
    if (levelOrderTraversal.length === 0) {
        return null;
    }
    if (levelOrderTraversal.length === 1) {
        // Technically this allows the root node to have `null` as its value.
        // I am okay with this.
        return new BinaryTree(levelOrderTraversal[0])
    }
    const levels = [[levelOrderTraversal[0]]]
    let i = 1;
    while (i < levelOrderTraversal.length) {
        const levelStart = i
        const levelEnd = i * 2 + 1
        const myLevel = levelOrderTraversal.slice(levelStart, levelEnd)
        while (myLevel.length < levelEnd - levelStart) {
            // handles incomplete input
            myLevel.push(null);
        }
        levels.push(myLevel)
        i = levelEnd
    }

    // Instantiate root with children
    const root = new BinaryTree(
        levels[0][0],
        levels[1][0] && new BinaryTree(levels[1][0]),
        levels[1][1] && new BinaryTree(levels[1][1])
    )

    let prev = [root.left, root.right];
    for (let i = 2; i < levels.length; i ++) {
        const level = levels[i]

        // Handle completely null level.
        if (level.every(val => val === null)) {
            if (i !== levels.length - 1) {
                throw new TypeError("Children supplied after entirely null level. Cannot build tree.")
            }
            break
        }

        const next = []
        for (let j = 0; j < prev.length; j ++) {
            const cur = prev[j]
            const leftVal = level[j * 2]
            const rightVal = level[j * 2 + 1]
            for (let [child, val] of [["left", leftVal], ["right", rightVal]]) {
                if (val === null) {
                    next.push(null)
                    continue
                }
                if (cur === null) {
                    throw new TypeError(`Not null child value ${val} supplied to null parent. Cannot build tree.`)
                }
                cur[child] = new BinaryTree(val);
                next.push(cur[child])
            }
        }
        prev = next
    }
    return root
}

BinaryTree.fromObj = function fromObj(obj) {
    if (obj === null) {
        return null
    }
    return new BinaryTree(obj.val, fromObj(obj.left), fromObj(obj.right))
}