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

TreeNode

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

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.

Iterating a node (via iterator, or the lazy asSequence/preOrderSequence extensions) visits the node and all of its descendants. Traversal and the height/nodeCount/clear helpers are implemented iteratively, so they are safe on arbitrarily deep trees.

Not thread-safe. Nodes are mutable (addChild/removeChild/clear mutate the structure and parent pointers). Sharing a tree across threads requires external synchronization, and the tree must not be modified while it is being iterated.

Equality is by reference (identity); use the structurallyEquals extension to compare two trees by value and shape.

Parameters

value

the value stored in this node.

treeIterator

the default traversal order used by iterator. Prefer the asSequence(order) / preOrderSequence() extensions to choose an order without mutating state.

Constructors

TreeNode

constructor(value: T, treeIterator: TreeNodeIterators = PreOrder)

Properties

children

val children: List<TreeNode<T>>

A group of nodes with the same parent.

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.

isRoot

val isRoot: Boolean

Checks whether the current tree node is the root of the tree

parent

val parent: TreeNode<T>?

The converse notion of a child, an immediate ancestor.

treeIterator

val treeIterator: TreeNodeIterators

value

val value: T

Functions

addChild

fun addChild(child: TreeNode<T>)

Adds child as a direct child of this node.

addChildren

fun addChildren(vararg children: TreeNode<T>)

Adds each of children as a direct child of this node, in order, validating each one the same way as addChild.

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 }.

child

open override fun child(value: T, childDeclaration: ChildDeclaration<T>? = null): TreeNode<T>

This method is used to easily create child in node.

clear

fun clear()

Removes every descendant of this node. Afterwards children is empty and all former descendants are detached (their parent is null). This node itself stays attached to its own parent.

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).

depth

fun depth(): Int

Distance is the number of edges along the shortest path between two nodes.

descendants

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

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

detach

fun detach(): Boolean

Detaches this node from its parent, removing it from the parent's children.

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.

height

fun height(): Int

insertChild

fun insertChild(index: Int, child: TreeNode<T>)

Inserts child as a direct child of this node at the given index, shifting any existing children at and after index one position to the right.

iterator

open operator override fun iterator(): Iterator<TreeNode<T>>

Returns an iterator over this node and its descendants using the default treeIterator order. Use iterator with an explicit order, or the asSequence(order) extension, to traverse in a different order without changing this node's default.

fun iterator(order: TreeNodeIterators): Iterator<TreeNode<T>>

Returns an iterator over this node and its descendants in the given order.

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.

moveChild

fun moveChild(child: TreeNode<T>, toIndex: Int): Boolean

Moves an existing direct child to a new position within this node's children.

nodeCount

fun nodeCount(): Int

This function go through tree and counts children. Root element is not counted.

path

fun path(descendant: TreeNode<T>): List<TreeNode<T>>?

Returns the chain of nodes from descendant up to and including this node, or null if descendant is not a strict descendant of this node.

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 prettyString(): String

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.

removeChild

fun removeChild(child: TreeNode<T>): Boolean

Removes child from this node's direct children, if present.

removeChildAt

fun removeChildAt(index: Int): TreeNode<T>

Removes the direct child at the given index, detaching it (its parent becomes null).

replaceChild

fun replaceChild(index: Int, child: TreeNode<T>): TreeNode<T>

Replaces the direct child at the given index with child, detaching the previous child (its parent becomes null).

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.

sortChildren

fun sortChildren(comparator: Comparator<TreeNode<T>>)

Sorts this node's direct children in place according to the given comparator. Only the immediate children are reordered; their subtrees are left untouched.

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.

toString

open override fun toString(): String