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

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

[sourcecode=java]
/*
We're building a tree that looks like this:

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

GenericTree tree = new GenericTree();

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

childD.addChild(childE);

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

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

tree.setRoot(root);
[/sourcecode]

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

TestGenericTreeNode.java

[sourcecode="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 node = new GenericTreeNode();
assertNull(node.getData());
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

}

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

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

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

@Test
public void TestNodeAddAndRemoveChildAt() {
GenericTreeNode node = new GenericTreeNode("root");
GenericTreeNode child1 = new GenericTreeNode("child1");
GenericTreeNode child2 = new GenericTreeNode("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 node = new GenericTreeNode();
GenericTreeNode child = new GenericTreeNode();

node.addChildAt(5, child);
}

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

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

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

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

GenericTreeNode child = new GenericTreeNode();
child.setData("child");

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

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

GenericTreeNode child1 = new GenericTreeNode();
child1.setData("child1");

GenericTreeNode child2 = new GenericTreeNode();
child2.setData("child2");

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

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

TestGenericTree.java
[sourcecode lang="java"]
import org.testng.annotations.Test;
import java.util.*;
import static org.testng.Assert.*;

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

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

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

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

assertFalse(tree.exists(nodeToFind));
}

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

assertNull(tree.find(nodeToFind));
}

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

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

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

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

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

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

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

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

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

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

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

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

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

assertNotNull(tree.getRoot());
}

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

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

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

assertFalse(tree.isEmpty());
}

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

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

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

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

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

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

@Test
void TestPostOrderBuildWithDepthSizeIsOneWithNonNullRoot() {
GenericTree tree = new GenericTree();
GenericTreeNode root = new GenericTreeNode("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 tree = new GenericTree();

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

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

tree.setRoot(rootA);

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

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

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

tree.setRoot(rootA);

GenericTreeNode nodeToFindD = new GenericTreeNode("D");

assertTrue(tree.exists(nodeToFindD));
}

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

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

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

tree.setRoot(rootA);

GenericTreeNode nodeToFindD = new GenericTreeNode("D");

assertNotNull(tree.find(nodeToFindD));
}

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

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

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

tree.setRoot(rootA);

GenericTreeNode nodeToFindE = new GenericTreeNode("E");

assertFalse(tree.exists(nodeToFindE));
}

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

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

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

tree.setRoot(rootA);

GenericTreeNode nodeToFindE = new GenericTreeNode("E");

assertNull(tree.find(nodeToFindE));
}

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

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

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

tree.setRoot(rootA);

List> preOrderList = new ArrayList>();
preOrderList.add(new GenericTreeNode("A"));
preOrderList.add(new GenericTreeNode("B"));
preOrderList.add(new GenericTreeNode("C"));
preOrderList.add(new GenericTreeNode("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 tree = new GenericTree();

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

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

tree.setRoot(rootA);

List> postOrderList = new ArrayList>();
postOrderList.add(new GenericTreeNode("B"));
postOrderList.add(new GenericTreeNode("D"));
postOrderList.add(new GenericTreeNode("C"));
postOrderList.add(new GenericTreeNode("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 tree = new GenericTree();

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

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

tree.setRoot(rootA);

Map, Integer> preOrderMapWithDepth = new LinkedHashMap, Integer>();
preOrderMapWithDepth.put(new GenericTreeNode("A"), 0);
preOrderMapWithDepth.put(new GenericTreeNode("B"), 1);
preOrderMapWithDepth.put(new GenericTreeNode("C"), 1);
preOrderMapWithDepth.put(new GenericTreeNode("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 tree = new GenericTree();

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

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

tree.setRoot(rootA);

Map, Integer> postOrderMapWithDepth = new LinkedHashMap, Integer>();
postOrderMapWithDepth.put(new GenericTreeNode("B"), 1);
postOrderMapWithDepth.put(new GenericTreeNode("D"), 2);
postOrderMapWithDepth.put(new GenericTreeNode("C"), 1);
postOrderMapWithDepth.put(new GenericTreeNode("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 tree = new GenericTree();

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

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

tree.setRoot(rootA);

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

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

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

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

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

tree.setRoot(rootA);

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

assertEquals(tree.toStringWithDepth(), preOrderMapWithDepth.toString());
}
}
[/sourcecode]

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

Pages: 1 2 3

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

Comments navigation

Older comments
  1. Pingback: Answer: Java tree data-structure? #answer #programming #computers | IT Info
  2. max says:
    November 5, 2015 at 7:44 pm

    This looks great! Just added to my project… you’re a life saver Vivin!

    Reply
  3. SUDHARSHAN REDDY KAKUMANU says:
    June 1, 2016 at 9:49 pm

    How do we get parent of a child ?

    Reply

Comments navigation

Older 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