Overview

The gen-tree repository holds a generic model for simple and binary tree objects. It is the reference Java implementation of ITree<V, T>: mutable, parent-pointer nodes with navigation, search, mutation and traversal built in. A TypeScript redesign of the same model — immutable nodes, copy-on-write mutation, generator-based traversal — lives in tree-kit.

Node types

Type	Shape	Use it when
BaseTreeNode<V, K>	value V, id K, parent pointer, children collection	the default choice — id-addressable nodes with the full ITree contract
TreeNode<V>	value V, parent pointer, children collection, no separate id	the value itself is identity enough
SimpleTreeNode<V, K>	leftmost-child / right-sibling links instead of a children collection	many siblings, memory matters more than O(1) child access
TreeIdNode<T, K>	id, parentId, childrenIds — ids only, no object references	persistence: the only one of these that is cycle-free and directly serialisable

All but TreeIdNode implement IBaseTreeNode<V, K, T> / ITreeNode<V, T>, which extend ITree<V, T> and add the visitor accept() plus id-aware findById().

Quick start

BaseTreeNode<String, Long> root = BaseTreeNode.<String, Long> builder().id(1L).value("root").build();
BaseTreeNode<String, Long> child = BaseTreeNode.<String, Long> builder().id(2L).value("child").build();
root.addChild(child);

root.isRoot();      // true
child.getLevel();   // 1
child.getParent();  // root
root.getAllSiblings(); // siblings in the parent's children collection

Traversal

accept(Visitor<T>) is post-order by default — every child is visited before its parent:

root.accept(node -> System.out.println(node.getValue())); // child, then root

For pre-order (parent before its children), go through the static handler directly with visitBefore = true:

BaseTreeNodeVisitorHandlerExtensions.accept(root, node -> System.out.println(node.getValue()), true);

traverse() and toList() collect the same post-order walk into a Collection<T> / List<T>; findByValue(V) / findAllByValue(V) search it for a matching value.

Query and transform utilities

Added alongside the tree-kit port — same vocabulary as its height / lowestCommonAncestor / filterTree / cloneSubtree / reduceTree, adapted to this library's mutable node model (filterTree mutates the tree in place here; tree-kit's copy-on-write equivalent returns a new one):

root.height();                                      // 0 for a leaf, deepest descent below this node
root.lowestCommonAncestor(otherNode);                // deepest shared ancestor, or null if unrelated
root.filterTree(node -> node.getValue() != null);    // keep matches, promote a dropped node's survivors
root.cloneSubtree(node -> node.toBuilder().build());  // deep, detached copy from a caller-supplied node copier
root.reduceTree(0, (count, node) -> count + 1, TraversalType.PREORDER); // fold, the tree-shaped Stream.reduce

filterTree is a reparenting filter, not a subtree prune: when a node fails the predicate, its surviving descendants are promoted to the nearest surviving ancestor instead of being dropped with it — the behaviour findAllByValue cannot give you, since that returns a flat list rather than a tree. cloneSubtree needs a node-copier because a generic type parameter cannot be instantiated directly; node.toBuilder().build() is safe to use as one even though Lombok's toBuilder() initially carries over the source's children collection by reference — cloneSubtree replaces it with a fresh collection before ever touching it, rather than clearing it in place, so the source tree is never mutated through that shared reference.

Every method above is also available as a static utility taking the node explicitly, for callers that prefer it: ITreeNodeHandlerExtensions.height(node), .lowestCommonAncestor(a, b), .filterTree(node, predicate), .cloneSubtree(node, copier), .reduceTree(node, seed, accumulator, traversalType).

Flat ⇄ tree conversion

BaseTreeNodeTransformer converts a BaseTreeNode tree to and from TreeIdNode — the id-only shape a database row or a JSON document can hold without cycles:

Map<Long, TreeIdNode<String, Long>> flat = BaseTreeNodeTransformer.toKeyMap(root);
Map<Long, BaseTreeNode<String, Long>> rebuilt = BaseTreeNodeTransformer.transform(flat);
BaseTreeNode<String, Long> rebuiltRoot = BaseTreeNodeTransformer.getRoot(flat);

transform fails loudly instead of producing a corrupt tree: a duplicate id, a parentId that names no row, an unknown childrenIds reference, or a cycle among the given TreeIdNode objects all throw IllegalStateException naming the offending id — the same defects tree-kit's buildTreeFromFlat rejects on the TypeScript side.

Please support this project by simply putting a Github

> Star ⭐ > > Share this library with friends on Twitter and everywhere else you can > > If you love this > project [](https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=GVBTWLRAZ7HB8)

License

The source code comes under the liberal MIT License, making gen-tree great for all types of applications.

Import dependencies to your project

gradle (click to expand)

gradle dependency

Replace the variable ${latestVersion} with the current latest version:

You can first define the version in the ext section and add than the following gradle dependency to your project build.gradle if you want to import the core functionality of gen-tree:

define version in file gradle.properties

genTreeVersion=${latestVersion}

or in build.gradle ext area

    genTreeVersion = "${latestVersion}"

then add the dependency to the dependencies area

    implementation("io.github.astrapi69:gen-tree:$genTreeVersion")

with new libs.versions.toml file

If you use the new libs.versions.toml file for new automatic catalog versions update

[versions]
gen-tree-version= "${latestVersion}"

[libraries]
gen-tree = { module = "io.github.astrapi69:gen-tree", version.ref = "gen-tree-version" }

then add the dependency to the dependencies area

    implementation libs.gen.tree

Maven (click to expand)

Maven dependency

Maven dependency is on the Sonatype Central Portal. Check out the Central Portal listing for latest releases.

Add the following maven dependency to your project pom.xml if you want to import the core functionality of gen-tree:

Then you can add the dependency to your dependencies:

<properties>
    ...

        <!-- gen-tree version -->
<gen-tree.version>${latestVersion}</gen-tree.version>

    ...
</properties>
    ...
    <dependencies>
    ...

            <!-- gen-tree DEPENDENCY -->
<dependency>
    <groupId>io.github.astrapi69</groupId>
    <artifactId>gen-tree</artifactId>
    <version>${gen-tree.version}</version>
</dependency>

    ...
    </dependencies>

Snapshots (click to expand)

📸 Snapshots

Snapshots are published to the Sonatype Central Portal's snapshot repository: central.sonatype.com/repository/maven-snapshots

This section describes how to import snapshot versions into your project. Add the following code snippet to your gradle file in the repositories section:

repositories {
   //...

    maven {
    name "Sonatype Nexus Snapshots"
    url "https://central.sonatype.com/repository/maven-snapshots"
    mavenContent {
        snapshotsOnly()
    }
}

}

Semantic Versioning

The versions of gen-tree are maintained with the Semantic Versioning guidelines.

Release version numbers will be incremented in the following format:

<major>.<minor>.<patch>

For detailed information on versioning you can visit the wiki page.

Want to Help and improve it?

The source code for gen-tree are on GitHub. Please feel free to fork and send pull requests!

Create your own fork of astrapi69/gen-tree/fork

To share your changes, submit a pull request.

Don't forget to add new units tests on your changes.

Contacting the Developers

Do not hesitate to contact the gen-tree developers with your questions, concerns, comments, bug reports, or feature requests.

• Feature requests, questions and bug reports can be reported at the issues page.

Note

No animals were harmed in the making of this library.

Donations

This project is kept as an open source product and relies on contributions to remain being developed. If you like this library, please consider a donation

over paypal:



or over bitcoin(BTC) with this address:

bc1ql2y99q7e8psndhcc3gferk03esw3qqf677rhjy

or over FIO with this address:

FIO7tFMUVAA9cHiPPqKMfMXiSxHrbpiFyRYqTketNuM67aULuwjop

or over Ethereum(ETH) with:

0xc057D159D3C8f3311E73568b334FF6fE82EB2b7D

or over Ethereum Classic(ETC) with:

0xF708cA86D86C246B69c3F4BAe431eBbe0c2bfddD

or over Dogecoin(DOGE) with:

D5yi4Um8cpakd6yPRm2hGWuQ5nrVzhSSW1

or over Monero(XMR) with:

49bqeRQ7Bf49oJFVC72pqpe5hFbb62pfXDYPdLsadGGF81KZW2ZfrPZ8PbAVu5X2v1TYAspeczMya3cYQysNS4usRRPQHVw

or over flattr:

Similar projects

• tree-api The ITree<V, T> interface this library implements
• tree-kit TypeScript sibling: immutable nodes, copy-on-write mutation, generator traversal
• Tree Data Structure Java Library This Library contains different implementations of the tree data structures, such as K-ary, binary, expression trees etc.
• Sample tree structure Sample tree structure for C# / Java with iterator and search

Credits

Sonatype Central Portal
Special thanks to Sonatype for providing a free maven repository service for open source projects

codecov.io
Special thanks to codecov.io for providing a free code coverage for open source projects

javadoc.io
Special thanks to javadoc.io for providing a free javadoc documentation for open source projects