Generic (n-ary) Tree in Java

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:

The code for a Generic Tree Node looks like this:

GenericTreeNode.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]

After writing a class for a Generic Tree Node, we need to write a Generic Tree class, which will use Generic Tree Nodes to build a Generic Tree:

GenericTreeTraversalOrderEnum.java

public enum GenericTreeTraversalOrderEnum { PRE_ORDER, POST_ORDER } [/sourcecode]

GenericTree.java

import java.util.*;

public class GenericTree {

private GenericTreeNode root;

public GenericTree() {
    super();
}

public GenericTreeNode getRoot() {
    return this.root;
}

public void setRoot(GenericTreeNode root) {
    this.root = root;
}

public int getNumberOfNodes() {
    int numberOfNodes = 0;

if(root != null) {
    numberOfNodes = auxiliaryGetNumberOfNodes(root) + 1; //1 for the root!
}

    return numberOfNodes;
}

private int auxiliaryGetNumberOfNodes(GenericTreeNode node) {
    int numberOfNodes = node.getNumberOfChildren();

for(GenericTreeNode child : node.getChildren()) {
    numberOfNodes += auxiliaryGetNumberOfNodes(child);
}

    return numberOfNodes;
}

public boolean exists(GenericTreeNode nodeToFind) {
    return (find(nodeToFind) != null);
}

public GenericTreeNode find(GenericTreeNode nodeToFind) {
    GenericTreeNode returnNode = null;

if(root != null) {
    returnNode = auxiliaryFind(root, nodeToFind);
}

    return returnNode;
}

private GenericTreeNode auxiliaryFind(GenericTreeNode currentNode, GenericTreeNode nodeToFind) {
    GenericTreeNode returnNode = null;
    int i = 0;

if (currentNode.equals(nodeToFind)) {
    returnNode = currentNode;
}

else if(currentNode.hasChildren()) {
    i = 0;
    while(returnNode == null && i < currentNode.getNumberOfChildren()) {
        returnNode = auxiliaryFind(currentNode.getChildAt(i), nodeToFind);
        i++;
    }
}

    return returnNode;
}

public boolean isEmpty() {
    return (root == null);
}

public List> build(GenericTreeTraversalOrderEnum traversalOrder) {
    List> returnList = null;

if(root != null) {
    returnList = build(root, traversalOrder);
}

    return returnList;
}

public List> build(GenericTreeNode node, GenericTreeTraversalOrderEnum traversalOrder) {
    List> traversalResult = new ArrayList>();

if(traversalOrder == GenericTreeTraversalOrderEnum.PRE_ORDER) {
    buildPreOrder(node, traversalResult);
}

else if(traversalOrder == GenericTreeTraversalOrderEnum.POST_ORDER) {
    buildPostOrder(node, traversalResult);
}

    return traversalResult;
}

private void buildPreOrder(GenericTreeNode node, List> traversalResult) {
    traversalResult.add(node);

    for(GenericTreeNode child : node.getChildren()) {
        buildPreOrder(child, traversalResult);
    }
}

private void buildPostOrder(GenericTreeNode node, List> traversalResult) {
    for(GenericTreeNode child : node.getChildren()) {
        buildPostOrder(child, traversalResult);
    }

    traversalResult.add(node);
}

public Map, Integer> buildWithDepth(GenericTreeTraversalOrderEnum traversalOrder) {
    Map, Integer> returnMap = null;

if(root != null) {
    returnMap = buildWithDepth(root, traversalOrder);
}

    return returnMap;
}

public Map, Integer> buildWithDepth(GenericTreeNode node, GenericTreeTraversalOrderEnum traversalOrder) {
    Map, Integer> traversalResult = new LinkedHashMap, Integer>();

if(traversalOrder == GenericTreeTraversalOrderEnum.PRE_ORDER) {
    buildPreOrderWithDepth(node, traversalResult, 0);
}

else if(traversalOrder == GenericTreeTraversalOrderEnum.POST_ORDER) {
    buildPostOrderWithDepth(node, traversalResult, 0);
}

    return traversalResult;
}

private void buildPreOrderWithDepth(GenericTreeNode node, Map, Integer> traversalResult, int depth) {
    traversalResult.put(node, depth);

    for(GenericTreeNode child : node.getChildren()) {
        buildPreOrderWithDepth(child, traversalResult, depth + 1);
    }
}

private void buildPostOrderWithDepth(GenericTreeNode node, Map, Integer> traversalResult, int depth) {
    for(GenericTreeNode child : node.getChildren()) {
        buildPostOrderWithDepth(child, traversalResult, depth + 1);
    }

    traversalResult.put(node, depth);
}

public String toString() {
    /*
    We're going to assume a pre-order traversal by default
     */

String stringRepresentation = "";

if(root != null) {
    stringRepresentation = build(GenericTreeTraversalOrderEnum.PRE_ORDER).toString();

    return stringRepresentation;
}

public String toStringWithDepth() {
    /*
    We're going to assume a pre-order traversal by default
     */

String stringRepresentation = "";

if(root != null) {
    stringRepresentation = buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER).toString();
}

        return stringRepresentation;
    }
}
[/sourcecode]

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 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!

Related

Maven project for Generic (n-ary) Tree in Java

Learning how to program in Oman in the 90's

Don't use class literals as type-tokens

Comments