Tree Data Structure/com.github.adriankuta.datastructure.tree

Package-level declarations

Types

ChildDeclaration

typealias ChildDeclaration<T> = ChildDeclarationInterface<T>.() -> Unit

ChildDeclarationInterface

interface ChildDeclarationInterface<T>

TreeConnectors

data class TreeConnectors(val branch: String, val vertical: String, val lastBranch: String, val empty: String)

The four glyph strings used to draw the tree branches in prettyString.

TreeNode

open class TreeNode<T>(val value: T, val treeIterator: TreeNodeIterators = PreOrder) : Iterable<TreeNode<T>> , ChildDeclarationInterface<T>

A node in a generic, mutable n-ary tree. Each node holds a value, a reference to its parent and an ordered list of children.

Properties

degree

val <T> TreeNode<T>.degree: Int

The number of direct children of this node.

isLeaf

val <T> TreeNode<T>.isLeaf: Boolean

true when this node has no children.

Functions

allNodes

fun <T> TreeNode<T>.allNodes(predicate: (T) -> Boolean): Boolean

true if every node's value matches predicate. Short-circuits.

ancestors

fun <T> TreeNode<T>.ancestors(): List<TreeNode<T>>

The chain of ancestors from the immediate parent up to (and including) the root.

anyNode

fun <T> TreeNode<T>.anyNode(predicate: (T) -> Boolean): Boolean

true if any node's value matches predicate. Short-circuits.

asSequence

fun <T> TreeNode<T>.asSequence(order: TreeNodeIterators = TreeNodeIterators.PreOrder): Sequence<TreeNode<T>>

Lazily traverses this subtree in the given order as a Sequence, without forcing the whole traversal up front. Pairs with the Kotlin stdlib, e.g. root.asSequence().map { it.value }.firstOrNull { it == target }.

contains

fun <T> TreeNode<T>.contains(value: T): Boolean

Returns true when this subtree contains a node whose value equals value, including the receiver itself. Values are compared with == (equals).

countNodes

fun <T> TreeNode<T>.countNodes(predicate: (T) -> Boolean): Int

Counts nodes whose value matches predicate.

deepCopy

fun <T> TreeNode<T>.deepCopy(): TreeNode<T>

Returns an independent deep copy of this subtree (same values, same shape, new nodes).

descendants

fun <T> TreeNode<T>.descendants(): List<TreeNode<T>>

All nodes in this subtree except this node, in pre-order.

distance

fun <T> TreeNode<T>.distance(other: TreeNode<T>): Int?

The number of edges on the shortest path between this node and other.

filterNodes

fun <T> TreeNode<T>.filterNodes(predicate: (T) -> Boolean): List<TreeNode<T>>

All nodes (pre-order) whose value matches predicate.

findNode

fun <T> TreeNode<T>.findNode(predicate: (T) -> Boolean): TreeNode<T>?

Returns the first node (pre-order) whose value matches predicate, or null. Short-circuits.

foldNodes

fun <T, R> TreeNode<T>.foldNodes(initial: R, operation: (acc: R, node: TreeNode<T>) -> R): R

Folds operation over all nodes in pre-order, starting from initial.

leaves

fun <T> TreeNode<T>.leaves(): List<TreeNode<T>>

All leaf nodes in this subtree, in pre-order.

levelOrderSequence

fun <T> TreeNode<T>.levelOrderSequence(): Sequence<TreeNode<T>>

Lazy level-order (breadth-first) traversal as a Sequence.

lowestCommonAncestor

fun <T> TreeNode<T>.lowestCommonAncestor(other: TreeNode<T>): TreeNode<T>?

The lowest (deepest) node that is an ancestor of both this node and other, where every node is considered an ancestor of itself.

mapValues

fun <T, R> TreeNode<T>.mapValues(transform: (T) -> R): TreeNode<R>

Returns a new tree with the same shape whose values are produced by transform. The original is left untouched. Stack-safe (iterative), so it handles arbitrarily deep trees.

pathBetween

fun <T> TreeNode<T>.pathBetween(other: TreeNode<T>): List<TreeNode<T>>?

The shortest path of nodes from this node to other, inclusive of both endpoints.

postOrderSequence

fun <T> TreeNode<T>.postOrderSequence(): Sequence<TreeNode<T>>

Lazy post-order traversal as a Sequence.

preOrderSequence

fun <T> TreeNode<T>.preOrderSequence(): Sequence<TreeNode<T>>

Lazy pre-order traversal as a Sequence.

prettyString

fun <T> TreeNode<T>.prettyString(connectors: TreeConnectors = TreeConnectors.Default, render: (value: T, depth: Int, isLast: Boolean) -> String = { value, _, _ -> "$value" }): String

Renders this subtree as a multi-line string, one node per line, with branch connectors.

root

fun <T> TreeNode<T>.root(): TreeNode<T>

Walks up the parent chain and returns the topmost ancestor (the tree root).

siblings

fun <T> TreeNode<T>.siblings(): List<TreeNode<T>>

The other children of this node's parent (excludes this node). Empty for the root.

structurallyEquals

fun <T> TreeNode<T>.structurallyEquals(other: TreeNode<T>): Boolean

Structural equality: true when other holds the same values in the same shape. Unlike TreeNode's reference equality, this compares the entire subtree. Stack-safe.

tree

inline fun <T> tree(root: T, defaultIterator: TreeNodeIterators = TreeNodeIterators.PreOrder, childDeclaration: ChildDeclaration<T>): TreeNode<T>

This method can be used to initialize new tree.