tree-structure-immutable/com.github.adriankuta.datastructure.tree.immutable/ImmutableTreeNode

ImmutableTreeNode

data class ImmutableTreeNode<T>(val value: T, val children: PersistentList<ImmutableTreeNode<T>> = persistentListOf())(source)

A node in an immutable, persistent n-ary tree. Each node holds a value and an ordered PersistentList of children; nodes never carry a parent back-reference, so a subtree is a self-contained, acyclic value.

Every mutating operation (addChild, removeChild, mapValues) returns a new root and leaves the receiver untouched. Subtrees that are not on the path of the change are reused as the same instances (structural sharing), so updates are cheap and old roots stay valid.

Equality is value-based: two nodes are equal when their values and children are equal (a data class), independent of identity.

Parameters

value

the value stored in this node.

children

the ordered, persistent list of child subtrees.

Constructors

ImmutableTreeNode

constructor(value: T, children: PersistentList<ImmutableTreeNode<T>> = persistentListOf())

Properties

children

val children: PersistentList<ImmutableTreeNode<T>>

value

val value: T

Functions

addChild

fun addChild(child: ImmutableTreeNode<T>): ImmutableTreeNode<T>

Returns a new node with child appended to this node's children. The receiver and every existing child subtree are reused unchanged (structural sharing).

height

fun <T> ImmutableTreeNode<T>.height(): Int

Returns the number of edges on the longest path between this node and a descendant leaf (0 for a leaf). Implemented iteratively, so it is safe on arbitrarily deep trees.

levelOrder

fun <T> ImmutableTreeNode<T>.levelOrder(): List<ImmutableTreeNode<T>>

Returns this subtree's nodes in level-order (breadth-first: the receiver, then its children, then their children, and so on). Implemented iteratively, so it is safe on arbitrarily deep trees.

mapValues

fun <R> mapValues(transform: (T) -> R): ImmutableTreeNode<R>

Returns a new tree of the same shape with every node's value transformed by transform. The receiver is not modified.

nodeCount

fun <T> ImmutableTreeNode<T>.nodeCount(): Int

Counts all descendants of this node; the receiver itself is not counted (matching the core TreeNode.nodeCount). Implemented iteratively, so it is safe on arbitrarily deep trees.

postOrder

fun <T> ImmutableTreeNode<T>.postOrder(): List<ImmutableTreeNode<T>>

Returns this subtree's nodes in post-order (each child subtree in order, then the receiver last). Implemented iteratively, so it is safe on arbitrarily deep trees.

preOrder

fun <T> ImmutableTreeNode<T>.preOrder(): List<ImmutableTreeNode<T>>

Returns this subtree's nodes in pre-order (the receiver first, then each child subtree in order). Implemented iteratively, so it is safe on arbitrarily deep trees.

removeChild

fun removeChild(child: ImmutableTreeNode<T>): ImmutableTreeNode<T>

Returns a new node with the first occurrence of child removed from this node's direct children, compared by value-based equality. If child is not a direct child, a structurally equal new node is returned. The receiver is never modified.