Generic (n-ary) Tree in Java

Creating the tree is pretty simple. Here is a snippet:

/*
 We're building a tree that looks like this:

 I am root!
     /\
    A B
      /\
     C D
         \
         E
*/

GenericTree<String> tree = new GenericTree<String>();

GenericTreeNode<String> root = new GenericTreeNode<String>("I am root!");
GenericTreeNode<String> childA = new GenericTreeNode<String>("A");
GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
GenericTreeNode<String> childD = new GenericTreeNode<String>("D");
GenericTreeNode<String> childE = new GenericTreeNode<String>("E");

childD.addChild(childE);

childB.addChild(childC);
childB.addChild(childD);

root.addChild(childA);
root.addChild(childB);

tree.setRoot(root);

Of course, simply writing a data structure is not enough. We need tests!

TestGenericTreeNode.java

import org.testng.annotations.Test;
import java.util.ArrayList;
import java.util.List;
import static org.testng.Assert.*;

public class TestGenericTreeNode {
    @Test
    public void TestNodeDataIsNullOnNewNodeCreation() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        assertNull(node.getData());
    }

    @Test
    public void TestNodeHasNonNullChildrenListOnNewNodeCreation() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        assertNotNull(node.getChildren());
    }

    @Test
    public void TestNodeHasZeroChildrenOnNewNodeCreation() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        assertEquals(node.getNumberOfChildren(), 0);
    }

    @Test
    public void TestNodeHasChildrenReturnsFalseOnNewNodeCreation() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        assertFalse(node.hasChildren());
    }

    @Test
    public void TestNodeDataIsNonNullWithParameterizedConstructor() {
        GenericTreeNode<String> node = new GenericTreeNode<String>("I haz data");
        assertNotNull(node.getData());
    }

    @Test
    public void TestNodeSetAndGetData() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        String data = "data";
        node.setData(data);
        assertEquals(node.getData(), data);
    }

    @Test
    public void TestNodeSetAndGetChildren() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        GenericTreeNode<String> child = new GenericTreeNode<String>();

        List<GenericTreeNode<String>> children = new ArrayList<GenericTreeNode<String>>();
        children.add(child);

        node.setChildren(children);
        assertEquals(node.getChildren(), children);
    }

    @Test
    public void TestNodeRemoveChildren() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        GenericTreeNode<String> child = new GenericTreeNode<String>();

        List<GenericTreeNode<String>> children = new ArrayList<GenericTreeNode<String>>();
        children.add(child);

        node.setChildren(children);
        node.removeChildren();
        assertEquals(node.getChildren().size(), 0);
    }

    @Test
    public void TestNodeAddChildHasOneChild() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        GenericTreeNode<String> child = new GenericTreeNode<String>();

        node.addChild(child);
        assertEquals(node.getNumberOfChildren(), 1);
    }

    @Test
    public void TestNodeAddChildHasChildrenIsTrue() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        GenericTreeNode<String> child = new GenericTreeNode<String>();

        node.addChild(child);
        assertTrue(node.hasChildren());

    }

    @Test
    public void TestNodeAddAndGetChildAt() {
        GenericTreeNode<String> node = new GenericTreeNode<String>("root");
        GenericTreeNode<String> child1 = new GenericTreeNode<String>("child1");
        GenericTreeNode<String> child2 = new GenericTreeNode<String>("child2");

        node.addChild(child1);
        node.addChildAt(1, child2);

        assertEquals(node.getChildAt(1).getData(), child2.getData());
    }

    @Test
    public void TestNodeAddAndRemoveChildAt() {
        GenericTreeNode<String> node = new GenericTreeNode<String>("root");
        GenericTreeNode<String> child1 = new GenericTreeNode<String>("child1");
        GenericTreeNode<String> child2 = new GenericTreeNode<String>("child2");

        node.addChild(child1);
        node.addChildAt(1, child2);

        node.removeChildAt(0);

        assertEquals(node.getNumberOfChildren(), 1);
    }

    @Test(expectedExceptions = java.lang.IndexOutOfBoundsException.class)
    public void TestNodeAddChildAtThrowsException() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        GenericTreeNode<String> child = new GenericTreeNode<String>();

        node.addChildAt(5, child);
    }

    @Test(expectedExceptions = java.lang.IndexOutOfBoundsException.class)
    public void TestNodeRemoveChildAtThrowsException() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        node.removeChildAt(1);
    }

    @Test
    public void TestNodeToString() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        node.setData("data");
        assertEquals(node.toString(), "data");
    }

    @Test
    public void TestNodeToStringVerboseNoChildren() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        node.setData("data");
        assertEquals(node.toStringVerbose(), "data:[]");
    }

    @Test
    public void TestNodeToStringVerboseOneChild() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        node.setData("data");

        GenericTreeNode<String> child = new GenericTreeNode<String>();
        child.setData("child");

        node.addChild(child);
        assertEquals(node.toStringVerbose(), "data:[child]");
    }

    @Test
    public void TestNodeToStringVerboseMoreThanOneChild() {
        GenericTreeNode<String> node = new GenericTreeNode<String>();
        node.setData("data");

        GenericTreeNode<String> child1 = new GenericTreeNode<String>();
        child1.setData("child1");

        GenericTreeNode<String> child2 = new GenericTreeNode<String>();
        child2.setData("child2");

        node.addChild(child1);
        node.addChild(child2);

        assertEquals(node.toStringVerbose(), "data:[child1, child2]");
    }
}

TestGenericTree.java

import org.testng.annotations.Test;
import java.util.*;
import static org.testng.Assert.*;

public class TestGenericTree {
    @Test
    public void TestRootIsNullOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();
        assertNull(tree.getRoot());
    }

    @Test
    public void TestNumberOfNodesIsZeroOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();
        assertEquals(tree.getNumberOfNodes(), 0);
    }

    @Test
    public void TestIsEmptyIsTrueOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();
        assertTrue(tree.isEmpty());
    }

    @Test
    void TestExistsIsFalseOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> nodeToFind = new GenericTreeNode<String>();

        assertFalse(tree.exists(nodeToFind));
    }

    @Test
    void TestFindReturnsNullOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> nodeToFind = new GenericTreeNode<String>();

        assertNull(tree.find(nodeToFind));
    }

    @Test
    void TestPreOrderBuildReturnsNullListOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();

        assertNull(tree.build(GenericTreeTraversalOrderEnum.PRE_ORDER));
    }

    @Test
    void TestPostOrderBuildReturnsNullListOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();

        assertNull(tree.build(GenericTreeTraversalOrderEnum.POST_ORDER));
    }

    @Test
    void TestPreOrderBuildWithDepthReturnsNullMapOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();

        assertNull(tree.buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER));
    }

    @Test
    void TestPostOrderBuildWithDepthReturnsNullMapOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();

        assertNull(tree.buildWithDepth(GenericTreeTraversalOrderEnum.POST_ORDER));
    }

    @Test
    void TestToStringReturnsEmptyStringOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();

        assertEquals(tree.toString(), "");
    }

    @Test
    void TestToStringWithDepthReturnsEmptyStringOnNewTreeCreation() {
        GenericTree<String> tree = new GenericTree<String>();

        assertEquals(tree.toStringWithDepth(), "");
    }

    @Test
    void TestSetRootGetRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>();
        tree.setRoot(root);

        assertNotNull(tree.getRoot());
    }

    @Test
    void TestNumberOfNodesIsOneWithNonNullRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>();
        tree.setRoot(root);

        assertEquals(tree.getNumberOfNodes(), 1);
    }

    @Test
    void TestEmptyIsFalseWithNonNullRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>();
        tree.setRoot(root);

        assertFalse(tree.isEmpty());
    }

    @Test
    void TestPreOrderBuildListSizeIsOneWithNonNullRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>("root");
        tree.setRoot(root);

        assertEquals(tree.build(GenericTreeTraversalOrderEnum.PRE_ORDER).size(), 1);
    }

    @Test
    void TestPostOrderBuildListSizeIsOneWithNonNullRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>("root");
        tree.setRoot(root);

        assertEquals(tree.build(GenericTreeTraversalOrderEnum.POST_ORDER).size(), 1);
    }

    @Test
    void TestPreOrderBuildWithDepthSizeIsOneWithNonNullRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>("root");
        tree.setRoot(root);

        assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER).size(), 1);
    }

    @Test
    void TestPostOrderBuildWithDepthSizeIsOneWithNonNullRoot() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> root = new GenericTreeNode<String>("root");
        tree.setRoot(root);

        assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.POST_ORDER).size(), 1);
    }

    /*
      Tree looks like:
          A
         / \
        B  C
            \
             D

      For the following tests

     */
    @Test
    void TestNumberOfNodes() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        assertEquals(tree.getNumberOfNodes(), 4);
    }

    @Test
    void TestExistsReturnsTrue() {
        GenericTree<String> tree = new GenericTree<String>();
        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        GenericTreeNode<String> nodeToFindD = new GenericTreeNode<String>("D");

        assertTrue(tree.exists(nodeToFindD));
    }

    @Test
    void TestFindReturnsNonNull() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        GenericTreeNode<String> nodeToFindD = new GenericTreeNode<String>("D");

        assertNotNull(tree.find(nodeToFindD));
    }

    @Test
    void TestExistsReturnsFalse() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        GenericTreeNode<String> nodeToFindE = new GenericTreeNode<String>("E");

        assertFalse(tree.exists(nodeToFindE));
    }

    @Test
    void TestFindReturnsNull() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        GenericTreeNode<String> nodeToFindE = new GenericTreeNode<String>("E");

        assertNull(tree.find(nodeToFindE));
    }

    // Pre-order traversal will give us A B C D
    @Test
    void TestPreOrderBuild() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        List<GenericTreeNode<String>> preOrderList = new ArrayList<GenericTreeNode<String>>();
        preOrderList.add(new GenericTreeNode<String>("A"));
        preOrderList.add(new GenericTreeNode<String>("B"));
        preOrderList.add(new GenericTreeNode<String>("C"));
        preOrderList.add(new GenericTreeNode<String>("D"));

        // Instead of checking equalities on the lists themselves, we can check equality on the toString's
        // they should generate the same toString's

        assertEquals(tree.build(GenericTreeTraversalOrderEnum.PRE_ORDER).toString(), preOrderList.toString());
    }

    //Post-order traversal will give us B D C A
    @Test
    void TestPostOrderBuild() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        List<GenericTreeNode<String>> postOrderList = new ArrayList<GenericTreeNode<String>>();
        postOrderList.add(new GenericTreeNode<String>("B"));
        postOrderList.add(new GenericTreeNode<String>("D"));
        postOrderList.add(new GenericTreeNode<String>("C"));
        postOrderList.add(new GenericTreeNode<String>("A"));

        // Instead of checking equalities on the lists themselves, we can check equality on the toString's
        // they should generate the same toString's

        assertEquals(tree.build(GenericTreeTraversalOrderEnum.POST_ORDER).toString(), postOrderList.toString());
     }

    //Pre-order traversal with depth will give us A:0, B:1, C:1, D:2
    @Test
    void TestPreOrderBuildWithDepth() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        Map<GenericTreeNode<String>, Integer> preOrderMapWithDepth = new LinkedHashMap<GenericTreeNode<String>, Integer>();
        preOrderMapWithDepth.put(new GenericTreeNode<String>("A"), 0);
        preOrderMapWithDepth.put(new GenericTreeNode<String>("B"), 1);
        preOrderMapWithDepth.put(new GenericTreeNode<String>("C"), 1);
        preOrderMapWithDepth.put(new GenericTreeNode<String>("D"), 2);

        // Instead of checking equalities on the maps themselves, we can check equality on the toString's
        // they should generate the same toString's

        assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER).toString(), preOrderMapWithDepth.toString());
     }

     //Post-order traversal with depth will give us B:1, D:2, C:1, A:0
    @Test
    void TestPostOrderBuildWithDepth() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        Map<GenericTreeNode<String>, Integer> postOrderMapWithDepth = new LinkedHashMap<GenericTreeNode<String>, Integer>();
        postOrderMapWithDepth.put(new GenericTreeNode<String>("B"), 1);
        postOrderMapWithDepth.put(new GenericTreeNode<String>("D"), 2);
        postOrderMapWithDepth.put(new GenericTreeNode<String>("C"), 1);
        postOrderMapWithDepth.put(new GenericTreeNode<String>("A"), 0);

        // Instead of checking equalities on the maps themselves, we can check equality on the toString's
        // they should generate the same toString's

        assertEquals(tree.buildWithDepth(GenericTreeTraversalOrderEnum.POST_ORDER).toString(), postOrderMapWithDepth.toString());
    }

    //toString and toStringWithDepth both use pre-order traversal
    @Test
    void TestToString() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        List<GenericTreeNode<String>> preOrderList = new ArrayList<GenericTreeNode<String>>();
        preOrderList.add(new GenericTreeNode<String>("A"));
        preOrderList.add(new GenericTreeNode<String>("B"));
        preOrderList.add(new GenericTreeNode<String>("C"));
        preOrderList.add(new GenericTreeNode<String>("D"));

        assertEquals(tree.toString(), preOrderList.toString());
    }

    @Test
    void TestToStringWithDepth() {
        GenericTree<String> tree = new GenericTree<String>();

        GenericTreeNode<String> rootA = new GenericTreeNode<String>("A");
        GenericTreeNode<String> childB = new GenericTreeNode<String>("B");
        GenericTreeNode<String> childC = new GenericTreeNode<String>("C");
        GenericTreeNode<String> childD = new GenericTreeNode<String>("D");

        childC.addChild(childD);
        rootA.addChild(childB);
        rootA.addChild(childC);

        tree.setRoot(rootA);

        Map<GenericTreeNode<String>, Integer> preOrderMapWithDepth = new LinkedHashMap<GenericTreeNode<String>, Integer>();
        preOrderMapWithDepth.put(new GenericTreeNode<String>("A"), 0);
        preOrderMapWithDepth.put(new GenericTreeNode<String>("B"), 1);
        preOrderMapWithDepth.put(new GenericTreeNode<String>("C"), 1);
        preOrderMapWithDepth.put(new GenericTreeNode<String>("D"), 2);

        assertEquals(tree.toStringWithDepth(), preOrderMapWithDepth.toString());
    }
}

That’s pretty much it. Hope you found this useful!

Popularity: 68% [?]

Pages: 1 2 3

January 30, 2010 - Posted by vivin | Java, Programming and Development | data structures, generic trees, java, k-ary trees, n-ary trees, programming, software engineering, trees (data structure)

37 Comments »

So what was the problem at work that necessitated this solution?
Reply

Comment by SteveO | January 30, 2010
@SteveO
I was trying to represent data that had parent-child relationships an arbitrary number of levels deep.
Reply

Comment by vivin | January 31, 2010
I believe it’s a rough implementation of your idea.
Which one do you prefer? Using Pattern, Matcher etc over -
return (this.children.size()>0? str.substring(0, str.lenth()-2) : str ) + “]”;
Reply

Comment by Lobo | February 1, 2010
@Lobo
I actually prefer the regex because it’s more obvious what I’m doing. When using a substring, it’s not immediately obvious (without comments) what you’re doing. I also gravitate towards to regexes due to the fact that I’ve written a lot of Perl code. Regexes aren’t as elegant in Java though.
Reply

Comment by vivin | February 1, 2010
Are you releasing this code as a project somewhere? It’d be nice to be able to simply include it as a library.
Reply

Comment by Guus | February 17, 2010
@Guus
Good point – I’ll try to jar it up sometime and release it as a library!
Reply

Comment by vivin | February 17, 2010
@vivin
Actually, I couldn’t wait and made a little Maven project out of it myself. I’ll be happy to send it to you, if you’d like me to.

There appears to be a small omission in the code: you’re not overriding Object.equals(Object obj) even though you intent to. Instead, you have GenericTreeNode.equals(GenericTreeNode obj).

Poke me via mail (I included it in the header of this comment) and I’ll send you a project archive.
Reply

Comment by Guus | February 17, 2010
@Guus
Ah, good point. Thanks for catching that! I’ll send you an email – thanks for taking the time to make a project. I do have a google code account – I should probably move this into that!
Reply

Comment by vivin | February 17, 2010
Hey,

Many companies have tons of Active Directory Groups, and there are group of groups, and it could be very tricky to assess how many group of groups there are.

I am trying to use your code in order to build a n-ary tree from these groups.

For each group stored in Active Directory there are :
- the members of this group it could “users” but also groups
- the groups that this group below to

I was wondering how to use your n-ary tree to build the n-ary trees in order to have a list of the trees and how deep they are. Any ideas ?

Many thanks, Oliver

I am using your code in order to build a tree from
Reply

Comment by oliver | August 24, 2010
I think the best way to go about it would be to create a Group object that maintains a list of Users. Then, your generic tree would be genericized by Group, meaning that the data element of each node is a Group object. This way you don’t need to represent Users as individual nodes. They can be wrapped up inside the Group object.

When you build up your tree, you first build up Group objects and add users to them. You then use the Group object to create a GenericTreeNode.
Reply

Comment by vivin | August 24, 2010
For over 4 hours, i was googling and trying different n-ary tree implementations. Yours was the best implementation!! you saved a lot of time.

Thanks
Reply

Comment by subbu | September 15, 2010
Vivin,Please send the enture source code as a zip file to deepakl_2000@yahoo.com
Reply

Comment by deepak | October 17, 2010
Hi Deepak. You can download the project zip from this page: http://vivin.net/2010/03/02/maven-project-for-generic-n-ary-tree-in-java/
Reply

Comment by Guus | October 18, 2010
Thanks
Reply

Comment by Deepak | October 18, 2010
Was just about to post the same!

@Guus I have a project on Github for a Tree collections library. I haven’t worked on it in a few months; I need to write some tests for it and also add a few more trees in there. You can take a look at it:

http://github.com/vivin/tree
Reply

Comment by vivin | October 18, 2010
You appear to forgot to include the pom.xml file.
Reply

Comment by Guus | October 18, 2010
@Guus
In the zip? Or for the project on github? Yeah that doesn’t have a pom (yet). It’s just up there while I’m working on it
Reply

Comment by vivin | October 18, 2010
Hey @Guus,
Can you write a main method so that i can go ahead and implement the tree structure in java,I have a homework assignment given for implementing a Tree structure,Do you think your implementation will serve purpose,Can you write a Public static main method such that Tree operations ,creation of parent and child relationship are possible and created and finnaly displayed
Reply

Comment by Deepak | October 18, 2010
@Deepak
You shouldn’t be asking others to do your homework for you. How will you learn anything then? If your homework asks you implement a tree, then you should do it yourself. Please do — you will learn more that way.
Reply

Comment by vivin | October 18, 2010
Thanks for the great implementation. I modified my local version to include one change:
I didnt like the fact that an external class can get hold of the children list and modify them without calling the classes addChild() like methods.

For instance;
GenericTreeNode tree = new GenericTreeNode();
List<GenericTreeNode> kids = new ArrayList<GenericTreeNode>();
kids.add(new GenericTreeNode(“bob”));

tree.setChildren(kids);
tree.getNumberOfChildren(); // returns 1
kids.add(new GenericTreeNode(“fred”));
tree.getNumberOfChildren(); // returns 2 even though addChild was not called!

So I redefined the following methods;
public void setChildren(List<GenericTreeNode> children) {
this.children = new ArrayList<GenericTreeNode>().addAll(children);
}
public List<GenericTreeNode> getChildren() {
return new ArrayList<GenericTreeNode>(this.children);
}

Thanks again…..

Bow
—–
Reply

Comment by bow | January 25, 2011
@bow
That’s a good modification and follows the best practice to make the class as immutable as possible. It must have slipped my mind I will modify the original to ensure that it makes defensive copies.
Reply

Comment by vivin | January 25, 2011
G’day mate,

Thanks for the library. I was halfway through making a similar class for a path planning library we are building at the university. I reckon I could use yours now. Though I have had to rename the package hierarchy for your classes, I have preserved your copyright statement and licence as well as have a put a link to this page in the source code. Our library is yet under development and once it’s tested, it’d be put into the public domain. I’ll post a link to it later here at your page.

Cheers,
Abhi

School of CS&IT, RMIT University
Reply

Comment by Abhi | January 27, 2011
@Abhi
Thanks! I don’t know if you checked it out, but Guus made a maven project for this library so you should be able to integrate it without having to change the package structure (depends on whether your library is mavenized or not, though).
Reply

Comment by vivin | January 29, 2011
Hi,
I need to recursively build a tree with an arbitrary number of children per node.
It turns out that I cannot get the parent of a GenericTreeNode. Is there any way to move from leaf to root in your implementation?
Thanks
Reply

Comment by jens | February 12, 2011
@jens
It’s funny you say that because I needed that very same functionality just yesterday! My current implementation does not offer that functionality, however it should be trivial to add. You just need a private property in GenericTreeNode:
```
private GenericTreeNode<T> parent;
```
and in the addChild method, set the parent of the new child node to this.
Reply

Comment by vivin | February 12, 2011
Hi Vivin,
Your Tree implementation was really useful for us in our compilers project for maintaining the relationship between various scopes in a program. Though we needed only a very small subset of Tree operations, your implementation provided a very good view into how to build an n-ary Tree in Java.
And like you said in your above post, I also needed the parent pointer in every node to traverse back from a node all the way upto the root.
Also, in line#69 in GenericTree.java, there is a redundant \i=0\ assignment. I guess you could remove that.

Thanks a lot
Reply

Comment by Akshay | April 1, 2011
@Akshay glad to be able to help
Reply

Comment by vivin | April 6, 2011
[...] Guus was kind enough to make a maven project for the Generic Tree. He also fixed an error in my equals method for the GenericTreeNode (I intended to do Object.equals(Object obj) but was doing GenericTreeNode.equals(GenericTreeNode obj). Since it’s a maven project, you can easily create a jar out of it and add it as a dependency to your project. You can download the project here. Thanks Guus! AKPC_IDS += "1405,";Popularity: unranked [?] Related PostsGeneric (n-ary) Tree in JavaCherryBlossomIntroducing CherryBlossomif-else in bAdkOdebAdkOde: An Esoteric LanguageJSTL, instanceof, and hasPropertyDuct-tape programmers are not heroesPerformance testing using The GrinderRunning the JavaFX 1.1 SDK on LinuxRunning the JavaFX 1.0 SDK on Linux Categories: Java, Programming and Development Tags: data structures, generic trees, java, k-ary trees, n-ary trees, programming, software engineering, trees (data structure) Comments (3) Trackbacks (0) Leave a comment Trackback [...]

Pingback by Maven project for Generic (n-ary) Tree in Java | Rough Book | May 25, 2011
hi

class GenericTreeNode.java line 68, put there keyword @Override and see if it compile.
Reply

Comment by miliardopiscrat | September 23, 2011
Here are two additional routines to allow searching for data.

public List<GenericTreeNode> locateOccurances(T data) {
List< GenericTreeNode > occurances = new ArrayList<GenericTreeNode>();
if (root != null) {
occurances.addAll( locateOccurances(root, data) );
}
return occurances;
}

public List<GenericTreeNode> locateOccurances(GenericTreeNode node, T data) {
List< GenericTreeNode > occurances = new ArrayList<GenericTreeNode>();

if (node.data == data) {
occurances.add(node);
}
for (GenericTreeNode child:node.children) {
occurances.addAll( locateOccurances(child, data) );
}
return occurances;
}
Reply

Comment by John Vorwald | December 11, 2011
Hi,

Probably I`m missing the point but what is the real purpose of build* methods? I mean, except for testing, why I would use a List<GenericTreeNode> ? BTW, I don’t think that “build” is the correct name. Can you “build a generic tree” ?

My $,02.

Cheers,

–FM
Reply

Comment by Fernando | December 11, 2011
@Fernando: The purpose of the “build” methods is to return a representation of the tree as a list in either preorder, or postorder form. The “buildWithDepth” returns a representation of the tree with the depths of the node as well, which is useful if you’re trying to provide a graphical representation of the tree.

In hindsight, I believe it would have been better to implement an iterator!
Reply

Comment by vivin | December 11, 2011
@John Vorwald: Thanks!
Reply

Comment by vivin | December 11, 2011
Thanks, vivin.

It was helpful. Implementation was easy and understandable much faster.
Reply

Comment by Manoj Rajan | January 9, 2012
Is this the latest implementation on this website. I believe this is exactly what im looking for in my project. Just to be clear this is a tree that can have any number of root nodes? also the T data that could also be anything? e.g. a simple string or a whole list of properties per say?
Reply

Comment by Devonte | February 23, 2012
main question though is that this can be more than just a binary tree? for example a quaternary tree where each node can lead to 4 options
Reply

Comment by Devonte | February 23, 2012
Could you possibly send me a method that iterates over the whole tree?
Reply

Comment by Devonte | February 24, 2012

Rough Book

random musings of just another computer nerd

Generic (n-ary) Tree in Java

37 Comments »

Leave a Comment Cancel reply

Search

Blogroll

Links

Recent Tweets

Recent Comments

Recent Trackbacks

Random Posts

Meta

Categories

Archives

Site info

Rough Book

random musings of just another computer nerd

Generic (n-ary) Tree in Java

37 Comments »

Leave a Comment Cancel reply

Search

Blogroll

Links

Popular Posts

Recent Tweets

Recent Comments

Recent Trackbacks

Random Posts

Tag Cloud

Category Cloud

Meta

Categories

Archives

Site info