Computes tidy, aesthetic tree layouts using the Walker (Buchheim–Jünger–Leipert) algorithm in O(n) time. Adapter-based traversal, variable node sizes, multiple orientations, outputs deterministic node coordinates.
⚠️ 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.
// build.gradle.kts
dependencies {
implementation("io.github.linde9821:treelayout-kmp:0.5.0")
}
TreeAdapter<T>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.
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(),
)
),
OrgNode(),
)
)
config = WalkerLayoutConfiguration(
horizontalDistance = ,
verticalDistance = ,
)
adapter = OrgTreeAdapter(ceo)
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.
TreeLayoutResult<T> provides chainable methods for adapting coordinates to your rendering target:
// Scale and center within a viewport
val fitted = result.centered(canvasWidth, canvasHeight)
// Flip Y for a canvas where Y grows downward
val flipped = result.scaledTo(800f, 600f).mapped { Point(it.x, 600f - it.y) }
// Arbitrary transform — rotation, padding, coordinate remapping
val padded = result.normalized().mapped { Point(it.x + 20f, it.y + 20f) }
All transformation methods return a new TreeLayoutResult<T> — the original is never mutated.
LayoutTransition<T> enables smooth animations between two layout states (e.g., when the tree structure changes):
import io.github.linde9821.treelayout.result.LayoutTransition
val transition = LayoutTransition(oldResult, newResult)
// Query which nodes are entering/exiting
transition.enteringNodes // nodes added in newResult
transition.exitingNodes // nodes removed from oldResult
// In your animation loop (framework-agnostic):
val frame = transition.interpolate(progress) // 0.0 → oldResult, 1.0 → newResult
In Jetpack Compose, drive progress with Animatable or animateFloatAsState and call interpolate each frame.
Zero-dependency JSON serialization for caching or transmitting layouts:
import io.github.linde9821.treelayout.result.toJson
import io.github.linde9821.treelayout.result.fromJson
// Serialize
val json = result.toJson { node -> node.id }
// Deserialize
val restored = TreeLayoutResult.fromJson(json) { id -> findNodeById(id) }
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 : <> {
: = node.name.length *
: =
}
result = WalkerTreeLayout(
adapter = OrgTreeAdapter(ceo),
configuration = WalkerLayoutConfiguration(horizontalDistance = , verticalDistance = ),
nodeExtentProvider = OrgExtentProvider(),
).layout()
The layout engine uses node extents to compute center-to-center distances:
width(left)/2 + horizontalDistance + width(right)/2By 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.
In addition to the linear Walker layout, the library includes two radial layout algorithms that arrange nodes in concentric circles around the root. These are useful when you want a compact, center-outward visualization — common for org charts, file explorers, and dependency graphs.
Package: io.github.linde9821.treelayout.radial.walker
This algorithm runs the Walker algorithm internally to determine sibling ordering and spacing, then maps the across-axis
(horizontal positions) to angular positions on concentric rings. Each depth level becomes a ring at radius
depth × layerDistance.
import io.github.linde9821.treelayout.radial.walker.RadialWalkerTreeLayout
import io.github.linde9821.treelayout.radial.walker.RadialWalkerLayoutConfiguration
val config = RadialWalkerLayoutConfiguration(
layerDistance = 80f,
margin = 0.5f, // radians subtracted from full circle to create a gap
rotation = 0.0f, // angular offset in radians
)
val result = RadialWalkerTreeLayout(
adapter = OrgTreeAdapter(ceo),
configuration = config,
).layout()
result.getPositions().forEach { (node, point) ->
println("${node.name} -> (, )")
}
The constructor accepts an optional nodeExtentProvider parameter, which is forwarded to the internal Walker pass for
variable-width node spacing:
val result = RadialWalkerTreeLayout(
adapter = OrgTreeAdapter(ceo),
configuration = config,
nodeExtentProvider = OrgExtentProvider(),
).layout()
Package: io.github.linde9821.treelayout.radial.angular
This algorithm recursively partitions angular space among children proportional to their subtree weight (total number of descendants including the child itself). It runs in O(n) — one pass to compute weights, one pass to assign positions. This produces evenly distributed layouts where larger subtrees receive proportionally more angular space.
import io.github.linde9821.treelayout.radial.angular.DirectAngularPlacementLayout
import io.github.linde9821.treelayout.radial.angular.DirectAngularPlacementConfiguration
val config = DirectAngularPlacementConfiguration(
layerDistance = 80f,
rotation = 0.0f, // angular offset in radians
)
val result = DirectAngularPlacementLayout(
adapter = OrgTreeAdapter(ceo),
configuration = config,
).layout()
result.getPositions().forEach { (node, point) ->
println("${node.name} -> (${point.x}, ${point.y})")
}
When to choose which?
Use Radial Walker when you want the Walker algorithm's aesthetic guarantees (symmetry, minimal width) projected onto a circle. Use Direct Angular Placement when you want a simpler, weight-proportional distribution with no dependency on the Walker pass.
TreeAdapter<T>WalkerLayoutConfigurationOrientation| Value | Description |
|---|---|
NodeExtentProvider<T>| Method | Description |
|---|---|
width(node: T): Float | Returns the width of a node. |
height(node: T): Float | Returns the height of a node. |
WalkerTreeLayout<T>| Method | Description |
|---|---|
layout(): TreeLayoutResult<T> | Executes the algorithm and returns positioned nodes. |
Constructor accepts an optional nodeExtentProvider parameter. When omitted, nodes are treated as dimensionless points
(backward compatible).
RadialWalkerLayoutConfigurationRadialWalkerTreeLayout<T>| Method | Description |
|---|---|
layout(): TreeLayoutResult<T> | Executes the algorithm and returns positioned nodes. |
Constructor parameters: adapter: TreeAdapter<T>, configuration: RadialWalkerLayoutConfiguration,
nodeExtentProvider: NodeExtentProvider<T> (optional, defaults to dimensionless points).
DirectAngularPlacementConfigurationDirectAngularPlacementLayout<T>| Method | Description |
|---|---|
layout(): TreeLayoutResult<T> | Executes the algorithm and returns positioned nodes. |
Constructor parameters: adapter: TreeAdapter<T>, configuration: DirectAngularPlacementConfiguration.
TreeLayoutResult<T>A concrete class representing the output of any layout algorithm. Can also be constructed directly for testing or custom
layout engines: TreeLayoutResult(positions: Map<T, Point>, maxDepth: Int).
LayoutTransition<T>Enables animated transitions between two layout states.
Extension functions in io.github.linde9821.treelayout.result:
| Function | Description |
|---|---|
TreeLayoutResult<T>.toJson(nodeToKey: (T) -> String): String | Serializes the layout to a JSON string. |
TreeLayoutResult.Companion.fromJson(json: String, keyToNode: (String) -> T): TreeLayoutResult<T> | Deserializes a layout from JSON. |
Point| Property | Type | Description |
|---|---|---|
x |
The layout is computed using the Buchheim–Jünger–Leipert improvement of the Walker algorithm, which guarantees:
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 features a dark-themed UI with a layout type selector (Walker / RadialWalker / DirectAngular) and
context-sensitive controls for each algorithm — orientation for Walker, margin and rotation for radial layouts. It
demonstrates variable node sizes 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.
| JVM | Android | iOS | macOS | tvOS | watchOS | Linux | Windows | JS | Wasm |
|---|
| ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
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
}
| Method | Description |
|---|
root(): T | Returns the root node of the tree. |
children(node: T): List<T> | Returns children in left-to-right order. |
parent(node: T): T? | Returns the parent, or null for the root. |
isLeaf(node: T): Boolean | Returns true if the node has no children. |
| Property | Type | Default | Description |
|---|
horizontalDistance | Float | 1.0f | Minimum spacing between sibling nodes. |
verticalDistance | Float | 1.0f | Spacing between depth levels. |
orientation | Orientation | Orientation.TopToBottom | Direction the tree grows from root. |
TopToBottom| Root at top, leaves grow downward. |
BottomToTop | Root at bottom, leaves grow upward. |
LeftToRight | Root at left, leaves grow rightward. |
RightToLeft | Root at right, leaves grow leftward. |
| Property | Type | Default | Description |
|---|
layerDistance | Float | 1.0f | Radial distance between concentric depth rings. |
margin | Float | 0.0f | Angular margin (in radians) subtracted from the full circle. |
rotation | Float | 0.0f | Angular offset (in radians) applied to all node positions. |
| Property | Type | Default | Description |
|---|
layerDistance | Float | 1.0f | Radial distance between concentric depth rings. |
rotation | Float | 0.0f | Angular offset (in radians) applied to all node positions. |
| Method | Description |
|---|
getPosition(node: T): Point | Returns the (x, y) coordinate for a node. |
getPositions(): Map<T, Point> | Returns all node-to-coordinate mappings. |
getMaxDepth(): Int | Returns the maximum depth of the laid-out tree. |
getBounds(): Bounds | Returns the axis-aligned bounding box of all positions. |
normalized(): TreeLayoutResult<T> | Shifts positions so the minimum corner is at the origin. |
translated(dx: Float, dy: Float): TreeLayoutResult<T> | Shifts all positions by the given offset. |
scaledTo(width: Float, height: Float): TreeLayoutResult<T> | Scales to fit within the given dimensions (preserves aspect ratio). |
centered(width: Float, height: Float): TreeLayoutResult<T> | Scales to fit and centers within a viewport. |
mapped(transform: (Point) -> Point): TreeLayoutResult<T> | Applies an arbitrary transform to all positions. |
| Member | Description |
|---|
LayoutTransition(from, to) | Constructor taking the start and end TreeLayoutResult. |
allNodes: Set<T> | All nodes in either state. |
persistentNodes: Set<T> | Nodes present in both states. |
enteringNodes: Set<T> | Nodes only in the end state. |
exitingNodes: Set<T> | Nodes only in the start state. |
interpolate(progress: Float): TreeLayoutResult<T> | Returns positions interpolated between start and end (0.0–1.0). |
Float |
| Horizontal position. |
y | Float | Vertical position (depth × verticalDistance). |
Surfaced from shared tags and platforms — no rankings paid for.