Jan 302010

This project is available on github. Please download from there to make sure you have the latest version.

Last week I was solving a problem at work that required the use of a Generic (n-ary) Tree. An n-ary tree is a tree where node can have between 0 and n children. There is a special case of n-ary trees where each node can have at most n nodes (k-ary tree). This implementation focuses on the most general case, where any node can have between 0 and n children. Java doesn’t have a Tree or Tree Node data structure. I couldn’t find any third-party implementations either (like in commons-lang). So I decided to write my own.

First, we need to define the node of our tree. Our node has two attributes. One is the data, and another is a List which can contain references to the children of that node:

Structure of a Generic Tree Node

Structure of a Generic Tree Node

The code for a Generic Tree Node looks like this:


import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class GenericTreeNode<T> {

    public T data;
    public List<GenericTreeNode<T>> children;

    public GenericTreeNode() {
        children = new ArrayList<GenericTreeNode<T>>();

    public GenericTreeNode(T data) {

    public List<GenericTreeNode<T>> getChildren() {
        return this.children;

    public int getNumberOfChildren() {
        return getChildren().size();

    public boolean hasChildren() {
        return (getNumberOfChildren() > 0);

    public void setChildren(List<GenericTreeNode<T>> children) {
        this.children = children;

    public void addChild(GenericTreeNode<T> child) {

    public void addChildAt(int index, GenericTreeNode<T> child) throws IndexOutOfBoundsException {
        children.add(index, child);

    public void removeChildren() {
        this.children = new ArrayList<GenericTreeNode<T>>();

    public void removeChildAt(int index) throws IndexOutOfBoundsException {

    public GenericTreeNode<T> getChildAt(int index) throws IndexOutOfBoundsException {
        return children.get(index);

    public T getData() {
        return this.data;

    public void setData(T data) {
        this.data = data;

    public String toString() {
        return getData().toString();

    public boolean equals(GenericTreeNode<T> node) {
        return node.getData().equals(getData());

    public int hashCode() {
        return getData().hashCode();

    public String toStringVerbose() {
        String stringRepresentation = getData().toString() + ":[";

        for (GenericTreeNode<T> node : getChildren()) {
            stringRepresentation += node.getData().toString() + ", ";

        //Pattern.DOTALL causes ^ and $ to match. Otherwise it won't. It's retarded.
        Pattern pattern = Pattern.compile(", $", Pattern.DOTALL);
        Matcher matcher = pattern.matcher(stringRepresentation);

        stringRepresentation = matcher.replaceFirst("");
        stringRepresentation += "]";

        return stringRepresentation;

  53 Responses to “Generic (n-ary) Tree in Java”

  1. […] wrote a little library that handles generic trees. It’s much more lightweight than the swing stuff. […]

Leave a Reply

All original content on these pages is fingerprinted and certified by Digiprove