Header image

Generic (n-ary) Tree in Java

Posted on by vivin

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!

Pages: 1 2 3
Category: Java, Programming and Development

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

  1. Pingback: Answer: Java tree data-structure? #answer #programming #computers | IT Info

Leave a Reply

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

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