buchheim

Compute compact layout of a rooted tree in linear time.

Originally described in Improving Walker's Algorithm to Run in Linear Time paper (OCR, explanation).

Based on this Python implementation.

Validated with property-based tests to conform to "good layout" rules from the paper (and some more).

Linear time is validated with benchmarking and statistics.

Usage

npm install buchheim

import { layout, normalize, type Tree } from "buchheim";

const tree: Tree<string> = {
    value: "root",
    children: [
        {
            value: "left",
            children: [],
        },
        {
            value: "right",
            children: [],
        },
    ],
};

// with root at 0
const positioned = layout(tree);

// with leftmost node at 0
const normalized = normalize(positioned);