Skip to content

Rough Book

random musings

Menu
  • About Me
  • Contact
  • Projects
    • bAdkOde
    • CherryBlossom
    • FXCalendar
    • Sulekha
Menu

Generic (n-ary) Tree in Java

Posted on January 30, 2010May 25, 2011 by vivin

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:

GenericTreeNode.java
[sourcecode lang="java"]
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class GenericTreeNode {

public T data;
public List> children;

public GenericTreeNode() {
super();
children = new ArrayList>();
}

public GenericTreeNode(T data) {
this();
setData(data);
}

public List> getChildren() {
return this.children;
}

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

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

public void setChildren(List> children) {
this.children = children;
}

public void addChild(GenericTreeNode child) {
children.add(child);
}

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

public void removeChildren() {
this.children = new ArrayList>();
}

public void removeChildAt(int index) throws IndexOutOfBoundsException {
children.remove(index);
}

public GenericTreeNode 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 node) {
return node.getData().equals(getData());
}

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

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

for (GenericTreeNode 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;
}
}
[/sourcecode]

Pages: 1 2 3

55 thoughts on “Generic (n-ary) Tree in Java”

Comments navigation

Newer comments
  1. SteveO says:
    January 30, 2010 at 11:24 pm

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

    Reply
  2. vivin says:
    January 31, 2010 at 10:26 am

    @SteveO
    I was trying to represent data that had parent-child relationships an arbitrary number of levels deep.

    Reply
  3. Lobo says:
    February 1, 2010 at 11:13 am

    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
  4. vivin says:
    February 1, 2010 at 4:10 pm

    @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
  5. Guus says:
    February 17, 2010 at 2:31 am

    Are you releasing this code as a project somewhere? It’d be nice to be able to simply include it as a library.

    Reply
  6. vivin says:
    February 17, 2010 at 9:20 am

    @Guus
    Good point – I’ll try to jar it up sometime and release it as a library!

    Reply
  7. Guus says:
    February 17, 2010 at 9:52 am

    @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
  8. vivin says:
    February 17, 2010 at 10:20 am

    @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
  9. oliver says:
    August 24, 2010 at 8:56 am

    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
  10. vivin says:
    August 24, 2010 at 9:07 am

    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
  11. subbu says:
    September 15, 2010 at 11:15 am

    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
  12. deepak says:
    October 17, 2010 at 6:14 am

    Vivin,Please send the enture source code as a zip file to [email protected]

    Reply
  13. Guus says:
    October 18, 2010 at 1:10 am

    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
  14. Deepak says:
    October 18, 2010 at 5:45 am

    Thanks

    Reply
  15. vivin says:
    October 18, 2010 at 9:16 am

    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
  16. Guus says:
    October 18, 2010 at 9:29 am

    You appear to forgot to include the pom.xml file.

    Reply
  17. vivin says:
    October 18, 2010 at 9:36 am

    @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
  18. Deepak says:
    October 18, 2010 at 10:37 am

    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
  19. vivin says:
    October 18, 2010 at 11:02 am

    @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
  20. bow says:
    January 25, 2011 at 5:19 pm

    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
  21. vivin says:
    January 25, 2011 at 6:11 pm

    @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
  22. Abhi says:
    January 27, 2011 at 7:34 pm

    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
  23. vivin says:
    January 29, 2011 at 10:09 am

    @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
  24. jens says:
    February 12, 2011 at 12:43 am

    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
  25. vivin says:
    February 12, 2011 at 11:11 am

    @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
  26. Akshay says:
    April 1, 2011 at 9:29 am

    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
    1. vivin says:
      April 6, 2011 at 9:39 am

      @Akshay glad to be able to help 🙂

      Reply
  27. Pingback: Maven project for Generic (n-ary) Tree in Java | Rough Book
  28. miliardopiscrat says:
    September 23, 2011 at 4:14 pm

    hi

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

    Reply
  29. John Vorwald says:
    December 11, 2011 at 5:48 am

    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
  30. Fernando says:
    December 11, 2011 at 10:14 am

    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
  31. vivin says:
    December 11, 2011 at 12:40 pm

    @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
  32. vivin says:
    December 11, 2011 at 12:42 pm

    @John Vorwald: Thanks!

    Reply
  33. Manoj Rajan says:
    January 9, 2012 at 4:54 am

    Thanks, vivin.

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

    Reply
  34. Devonte says:
    February 23, 2012 at 3:13 pm

    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
  35. Devonte says:
    February 23, 2012 at 4:28 pm

    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
  36. Devonte says:
    February 24, 2012 at 10:25 am

    Could you possibly send me a method that iterates over the whole tree?

    Reply
  37. Pingback: Making a dynamic sequence | PHP Developer Resource
  38. vivin says:
    June 10, 2012 at 1:32 pm

    @Devonte: Yes, it’s genericized and so T can be anything.

    This is a generic tree and so any node can have any number of nodes. It could be a binary or a quaternary tree, although not strictly so because no constraints are enforced on the number of children a node can have.

    Reply
  39. sam says:
    June 11, 2012 at 12:27 pm

    Could you please help me in solving this.

    http://www.careercup.com/question?id=13876713

    Reply
  40. Oka Prinarjaya says:
    October 16, 2012 at 1:51 am

    Mr. Vivin,

    Please help me. Can you help me?
    http://stackoverflow.com/questions/12910719/how-to-populating-modified-preorder-tree-traversal-data-into-java-tree-object

    Reply
  41. Pingback: How to populating Modified Preorder Tree Traversal data into Java tree object? | Jisku.com
  42. Pingback: How to populating Modified Preorder Tree Traversal data into Java tree object? - feed99
  43. Pingback: Did I create my Java Objects Correctly | Code and Programming
  44. JM says:
    December 31, 2012 at 10:18 am

    Hi Vivin, Can you structure be used even if I have nodes that are of different types? I have at least 5 different type of nodes one at each level. Please confirm!

    Reply
  45. vivin says:
    January 2, 2013 at 9:40 am

    @JM: Do you mean the generic type parameter? You can only add nodes that contain data of the type that you specify, when you create the node or the tree. However, you can get around this if all of those objects implement the same interface. But you have to make sure that it makes sense for all of them to use the same interface.

    Reply
  46. JM says:
    January 7, 2013 at 8:41 pm

    Thanks Vivin, that totally makes sense.

    However I noticed another issue while converting the tree (with several nodes) into JSON object for representing the tree on UI. Because every GenericTreeNode is having references to child and parent and every parent is intern having child and parent, it is going a infinite recursion while converting the tree into JSON object (Jackson JSON). I used annotations from http://wiki.fasterxml.com/JacksonFeatureBiDirReferences to avoid bidirectional references. But the problem is after converting the Tree into JSON this way, I loosing references to all parents. Any ideas to get rid of this problem? Thanks in advance!

    Reply
    1. HB says:
      October 22, 2014 at 9:02 pm

      Hey JM, did you figure out your JSON issue?
      Btw, are you displaying this Tree in a UI? What technology/library are you using?

      Thanks!

      Reply
  47. vivin says:
    January 14, 2013 at 11:00 am

    @JM: JSON is simply a notation and so it’s not functional. This is why it’s impossible to create self-referential constructs in JSON. The only way you can do it in an abstract manner, such as using an id to refer to a parent.

    Reply
  48. Dimid says:
    March 5, 2013 at 8:53 am

    Thanks! Great library. I’ve added the following method:

    public List getDataOfChildren() {
    List result = new ArrayList();
    for (GenericTreeNode child:this.children) {
    result.add(child.data);
    }

    return result;
    }

    Reply
  49. Pingback: How to: Java tree data-structure? | SevenNet
  50. Pingback: Fixed Java tree data-structure? #dev #it #asnwer | Good Answer

Comments navigation

Newer comments

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Meta

  • Log in
  • Entries feed
  • Comments feed
  • WordPress.org

Archives

  • February 2023
  • April 2020
  • February 2020
  • January 2020
  • December 2019
  • November 2019
  • September 2019
  • August 2019
  • July 2019
  • June 2019
  • May 2019
  • March 2019
  • February 2019
  • January 2019
  • December 2018
  • November 2018
  • September 2018
  • August 2018
  • July 2018
  • June 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • June 2017
  • March 2017
  • November 2016
  • August 2016
  • July 2016
  • June 2016
  • February 2016
  • August 2015
  • July 2014
  • June 2014
  • March 2014
  • December 2013
  • November 2013
  • September 2013
  • July 2013
  • June 2013
  • March 2013
  • February 2013
  • January 2013
  • October 2012
  • July 2012
  • June 2012
  • January 2012
  • December 2011
  • November 2011
  • October 2011
  • September 2011
  • July 2011
  • June 2011
  • May 2011
  • February 2011
  • January 2011
  • December 2010
  • November 2010
  • October 2010
  • September 2010
  • July 2010
  • June 2010
  • May 2010
  • April 2010
  • March 2010
  • January 2010
  • December 2009
  • November 2009
  • October 2009
  • September 2009
  • August 2009
  • July 2009
  • May 2009
  • April 2009
  • March 2009
  • February 2009
  • January 2009
  • December 2008
  • November 2008
  • October 2008
  • August 2008
  • March 2008
  • February 2008
  • November 2007
  • July 2007
  • June 2007
  • May 2007
  • March 2007
  • December 2006
  • October 2006
  • September 2006
  • August 2006
  • June 2006
  • April 2006
  • March 2006
  • January 2006
  • December 2005
  • November 2005
  • October 2005
  • September 2005
  • August 2005
  • July 2005
  • June 2005
  • May 2005
  • April 2005
  • February 2005
  • October 2004
  • September 2004
  • August 2004
  • July 2004
  • June 2004
  • May 2004
  • April 2004
  • March 2004
  • February 2004
  • January 2004
  • December 2003
  • November 2003
  • October 2003
  • September 2003
  • July 2003
  • June 2003
  • May 2003
  • March 2003
  • February 2003
  • January 2003
  • December 2002
  • November 2002
  • October 2002
  • September 2002
  • August 2002
  • July 2002
  • June 2002
  • May 2002
  • April 2002
  • February 2002
  • September 2001
  • August 2001
  • April 2001
  • March 2001
  • February 2001
  • January 2001
  • December 2000
  • November 2000
  • October 2000
  • August 2000
  • July 2000
  • June 2000
  • May 2000
  • March 2000
  • January 2000
  • December 1999
  • November 1999
  • October 1999
  • September 1999
©2023 Rough Book | Built using WordPress and Responsive Blogily theme by Superb
All original content on these pages is fingerprinted and certified by Digiprove