⚠️ This library is under active development and has not reached a stable release yet. The API may change between versions. Feedback and contributions are welcome.

A pure Kotlin Multiplatform library for computing tidy, aesthetically pleasing tree visualizations. It implements the Walker algorithm (Buchheim–Jünger–Leipert variant) in $O(n)$ time with zero platform dependencies — no JVM, Android, or iOS frameworks required.

TreeLayoutKMP works with any tree structure you already have. You provide a thin adapter describing how to traverse your nodes; the library computes optimal (x, y) coordinates for every node in the tree.

Note: This library is a layout engine, not a rendering library. It outputs coordinates — how you draw the tree (Canvas, SVG, Compose, HTML, etc.) is entirely up to you.

Try the live demo on GitHub Pages

// build.gradle.kts
dependencies {
    implementation("io.github.linde9821:treelayout-kmp:0.2.1")
}

The library is decoupled from any specific tree representation through the TreeAdapter<T> interface. This design means you never need to convert your domain model into a library-specific node class — you simply describe how to navigate it.

import io.github.linde9821.treelayout.TreeAdapter

// Your existing domain model — no modifications needed.
data class OrgNode(
    val name: String,
    val reports: List<OrgNode> = emptyList(),
    val manager: OrgNode? = null,
)

// Adapter bridges your model to the layout engine.
class OrgTreeAdapter(private val rootNode: OrgNode) : TreeAdapter<OrgNode> {
    override fun root(): OrgNode = rootNode
    override fun children(node: OrgNode): List<OrgNode> = node.reports
    override fun parent(node: OrgNode): OrgNode? = node.manager
}

Why an adapter pattern?
Tree structures vary wildly across domains — file systems, ASTs, org charts, UI component trees. Rather than forcing you to wrap every node in a library class, TreeAdapter<T> lets the layout engine traverse your data in-place. This keeps allocations minimal and avoids coupling your domain layer to a visualization concern.

import io.github.linde9821.treelayout.walker.WalkerTreeLayout
import io.github.linde9821.treelayout.walker.WalkerLayoutConfiguration

// Build your tree
val ceo = OrgNode(
    "CEO", reports = listOf(
        OrgNode(
            "VP Engineering", reports = listOf(
                OrgNode("Team Lead A"),
                OrgNode("Team Lead B"),
            )
        ),
        OrgNode("VP Design"),
    )
)

// Configure spacing (optional — defaults to 1.0 for both axes)
val config = WalkerLayoutConfiguration(
    horizontalDistance = 2.0f,
    verticalDistance = 1.5f,
)

// Compute the layout
val adapter = OrgTreeAdapter(ceo)
val result = WalkerTreeLayout(adapter, config).layout()

TreeLayoutResult<T> gives you access to computed coordinates:

// Get a single node's position
val ceoPos = result.getPosition(ceo)
println("CEO is at (${ceoPos.x}, ${ceoPos.y})")

// Iterate all positions — useful for rendering
result.getPositions().forEach { (node, point) ->
    println("${node.name} -> (${point.x}, ${point.y})")
}

// Query layout metadata
println("Tree depth: ${result.getMaxDepth()}")

Coordinates use a top-down orientation: the root is at y = 0, and depth increases downward by verticalDistance per level.

By default, nodes are treated as dimensionless points. For real-world trees where nodes have varying widths and heights (labels, icons, content boxes), provide a NodeExtentProvider<T> to prevent overlap:

import io.github.linde9821.treelayout.NodeExtentProvider

class OrgExtentProvider : NodeExtentProvider<OrgNode> {
    override fun width(node: OrgNode): Float = node.name.length * 10f
    override fun height(node: OrgNode): Float = 40f
}

val result = WalkerTreeLayout(
    adapter = OrgTreeAdapter(ceo),
    configuration = WalkerLayoutConfiguration(horizontalDistance = 20f, verticalDistance = 60f),
    nodeExtentProvider = OrgExtentProvider(),
).layout()

The layout engine uses node extents to compute center-to-center distances:

• Horizontal: width(left)/2 + horizontalDistance + width(right)/2
• Vertical: each level's y-offset accounts for the tallest node at the preceding level

By default, the tree grows top-to-bottom. Use the orientation property to change direction:

val config = WalkerLayoutConfiguration(
    horizontalDistance = 2.0f,
    verticalDistance = 1.5f,
    orientation = Orientation.LeftToRight, // tree grows left → right
)

val result = WalkerTreeLayout(adapter, config).layout()

Available orientations: TopToBottom, BottomToTop, LeftToRight, RightToLeft.

Constructor accepts an optional nodeExtentProvider parameter. When omitted, nodes are treated as dimensionless points (backward compatible).

The layout is computed using the Buchheim–Jünger–Leipert improvement of the Walker algorithm, which guarantees:

• O(n) time complexity — linear in the number of nodes.
• Aesthetic rules — nodes at the same depth are aligned, subtrees are non-overlapping, and the drawing is as narrow as possible while preserving symmetry.
• Deterministic output — the same tree always produces the same coordinates.

The benchmark/ module measures layout computation time across trees ranging from 1 to ~6 million nodes. Results confirm the algorithm's O(n) linear time complexity — computation time scales proportionally with node count.

Run the benchmark yourself:

./gradlew :benchmark:jvmRun

The sample/ module is a Compose Multiplatform application that visualizes a prefix tree built from user-provided words. It demonstrates variable node sizes, all four orientations, and interactive layout controls.

./gradlew :sample:run

Opens a window with a side panel for layout controls, a text input for words, and a zoomable tree canvas.

./gradlew :sample:wasmJsBrowserProductionRun

Launches a local dev server and opens the sample in your browser. This is the same app deployed to GitHub Pages.

The standalone Android sample lives in sample/android/. Open it in Android Studio and run on a device or emulator, or build from the command line:

cd sample/android
./gradlew installDebug

Open sample/iosApp/iosApp.xcodeproj in Xcode and run on a simulator or device. The shared Kotlin code is compiled into a static framework via the :sample module's iOS targets.

Apache License 2.0 — see LICENSE for details.