A general tree data structure in Java

Question

Introduction

I have this general tree data structure that imposes no restrictions on its topology: Any non-leaf node may have as many immediate children as desired. Also, there is no restrictions on how deep each branch goes either.

Code

TreeNode.java

package net.coderodde.util;

import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements a general tree node.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 27, 2018)
 * @param <E> the stored element type.
 */
public final class TreeNode<E> {
    
    /**
     * The element stored in this tree node. May be {@code null}.
     */
    private E element;
    
    /**
     * The parent node of this tree node. We need this in order to make sure
     * that there is no cycles, i.e., a node cannot be both its own predecessor
     * and successor.
     * 
     * This field is kept package-private so that the TODO
     */
    TreeNode<E> parent;
    
    /**
     * The set of child nodes. We will use {@link java.util.LinkedHashSet} for 
     * the child set implementation. While this allows adding/removing in 
     * average constant time, the child nodes will be ordered by their 
     * insertion order, i.e., if 'A' is first added to a specific tree node 'N', 
     * after which 'B' is added to 'N', when iterating over children of 'N', 'A'
     * will be always returned before 'B'.
     * 
     * This field is kept package-private so that the 
     * {@link TreeNodeChildrenView} can access the actual set of child tree
     * nodes.
     */
    Set<TreeNode<E>> children;
    
    /**
     * The view object over this tree node's children. It is kept 
     * package-private so that {@link TreeNodeChildrenView} can access it.
     */
    TreeNodeChildrenView<E> childrenView;
    
    /**
     * The constructor of this tree node.
     * 
     * @param element the element to set to this tree node. May be {@code null}.
     */
    TreeNode(E element) {
        this.element = element;
        this.parent = null;
    }
    
    /**
     * Adds a child tree node to this tree node. The new child will have a given
     * element.
     * 
     * @param element the element to set. May be {@code null}.
     * @return the newly created child node so that the client programmer can
     *         operate on it.
     */
    public TreeNode<E> addChild(E element) {
        if (children == null) {
            children = new LinkedHashSet<>();
            childrenView = new TreeNodeChildrenView<>(this);
        }
        
        TreeNode<E> child = new TreeNode<>(element);
        child.parent = this;
        children.add(child);
        return child;
    }
    
    /**
     * Returns the children of this tree node. The client programmer can
     * directly operate on this set, adding/removing tree nodes.
     * 
     * @return the children of this tree node. 
     */
    public TreeNodeChildrenView<E> getChildren() {
        if (children == null) {
            children = new LinkedHashSet<>();
            childrenView = new TreeNodeChildrenView<>(this);
        }
        
        return childrenView;
    }
    
    public E getElement() {
        return element;
    }
    
    public void setElement(E element) {
        this.element = element;
    }
    
    @Override
    public String toString() {
        return Objects.toString(element);
    }
}

TreeNodeChildrenView.java

package net.coderodde.util;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;

/**
 * This class provides a view over a tree nodes children. The client programmer
 * can manipulate it to his/her own liking.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 27, 2018)
 * @param <E> the tree node element type.
 */
public final class TreeNodeChildrenView<E> implements Set<TreeNode<E>> {

    /**
     * The tree node that owns this view.
     */
    private final TreeNode<E> ownerTreeNode;

    /**
     * Constructs this view for the input tree node.
     * 
     * @param ownerTreeNode the tree node this children view belongs to.
     */
    TreeNodeChildrenView(TreeNode<E> ownerTreeNode) {
        this.ownerTreeNode = ownerTreeNode;
    }

    /**
     * Returns the number of children in this view.
     * 
     * @return the number of children.
     */
    @Override
    public int size() {
        return ownerTreeNode.children.size();
    }

    /**
     * Returns {@code true} only if this view has no child tree nodes.
     * 
     * @return {@code true} if this view has no child tree nodes. 
     */
    @Override
    public boolean isEmpty() {
        return ownerTreeNode.children.isEmpty();
    }

    /**
     * Returns {@code true} only if this tree node children view contains a 
     * given tree node.
     * 
     * @param o the query tree node.
     * @return {@code true} only if {@code o} is in this view.
     */
    @Override
    public boolean contains(Object o) {
        if (o == null) {
            return false;
        } else if (!(o instanceof TreeNode)) {
            return false;
        } else {
            return ownerTreeNode.children.contains(o);
        }
    }

    /**
     * Returns an iterator over this view's children.
     * 
     * @return an iterator over this view's children.
     */
    @Override
    public Iterator<TreeNode<E>> iterator() {
        return ownerTreeNode.children.iterator();
    }

    @Override
    public boolean add(TreeNode<E> treeNode) {
        Objects.requireNonNull(treeNode, "The input tree node is null.");
        checkInputTreeNodeIsNotPredecessorOfThisTreeNode(treeNode);

        // Return {@code false} whenever the input tree node is already in this
        // tree.
        if (ownerTreeNode.children.contains(treeNode)) {
            return false;
        }

        // If the input tree node belongs to a parent, disconnect it from it:
        if (treeNode.parent != null) {
            treeNode.parent.children.remove(treeNode);
        }

        // Connect the input tree node as the child of this view.
        ownerTreeNode.children.add(treeNode);
        treeNode.parent = ownerTreeNode;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (o == null) {
            return false;
        } else if (!(o instanceof TreeNode)) {
            return false;
        }

        TreeNode<E> treeNode = (TreeNode<E>) o;
        treeNode.parent = null;
        return ownerTreeNode.children.remove(treeNode);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }

        return true;
    }

    @Override
    public boolean addAll(Collection<? extends TreeNode<E>> c) {
        boolean modified = false;

        for (TreeNode<E> treeNode : c) {
            if (add(treeNode)) {
                modified = true;
            }
        }

        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        int numberOfChildrenBefore = size();

        Set<?> collectionAsSet = 
                (c instanceof HashSet) ? (Set<?>) c : new HashSet(c);

        Iterator<TreeNode<E>> iterator =
                ownerTreeNode.children.iterator();

        while (iterator.hasNext()) {
            TreeNode<E> currentTreeNode = iterator.next();

            if (!collectionAsSet.contains(currentTreeNode)) {
                iterator.remove();
            }
        }

        return size() < numberOfChildrenBefore;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return ownerTreeNode.children.removeAll(c);
    }

    @Override
    public void clear() {
        ownerTreeNode.children.clear();
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException();
    }

    /**
     * Checks that the input tree node is not a predecessor of itself.
     * 
     * @param treeNode the tree node to check.
     */
    private void checkInputTreeNodeIsNotPredecessorOfThisTreeNode(
            TreeNode<E> treeNode) {
        TreeNode<E> currentTreeNode = ownerTreeNode;

        while (currentTreeNode != null) {
            if (currentTreeNode == treeNode) {
                throw new IllegalStateException(
                        "Trying to create a cycle in this tree.");
            }

            currentTreeNode = currentTreeNode.parent;
        }
    }
}

Tree.java

package net.coderodde.util;

/**
 * This class implements a general tree data structure.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 27, 2018)
 * @param <E> the tree node element type.
 */
public final class Tree<E> {

    /**
     * The root node. This node does not logically belong to this tree as it
     * merely provides a way of having multiple "roots". 
     */
    private final TreeNode<E> pseudoroot = new TreeNode<>(null);

    /**
     * Returns the root node. It is <b>not</b> considered to belong to the
     * actual tree. We merely want to have a way of attaching nodes to it.
     * 
     * @return the pseudoroot of this tree.
     */
    public TreeNode<E> getPseudoRoot() {
        return pseudoroot;
    }

    @Override
    public String toString() {
        return "";
    }
}

TreeToStringConverter.java

package net.coderodde.util;

/**
 * This interface defines API for converting generic trees to a textual format.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 7, 2018)
 */
public interface TreeToStringConverter<E> {

    /**
     * Converts the input tree into a textual format.
     * 
     * @param tree the tree to convert.
     * @return a textual representation of the input tree according to  the
     *         implementing format.
     */
    public String toString(Tree<E> tree);
}

SimpleTreeToStringConverter.java

package net.coderodde.util;

import java.util.Objects;

/**
 * This class implements a simple converter from a 
 * {@link net.coderodde.util.Tree} to a string.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 7, 2018)
 */
public final class SimpleTreeToStringConverter<E>
implements TreeToStringConverter<E> {

    /**
     * {@inheritDoc }
     */
    @Override
    public String toString(Tree<E> tree) {
        Objects.requireNonNull(tree, "The input tree is null.");
        StringBuilder stringBuilder = new StringBuilder();        

        for (TreeNode<E> root : tree.getPseudoRoot().getChildren()) {
            toString(stringBuilder, root, 0);
        }

        return stringBuilder.toString();
    }

    // Implements the actual conversion procedure.
    private void toString(StringBuilder stringBuilder, 
                          TreeNode<E> node,
                          int nodeDepth) {
        for (int i = 0; i < nodeDepth; i++) {
            stringBuilder.append(' ');
        }

        stringBuilder.append(Objects.toString(node.getElement()))
                     .append('\n');

        for (TreeNode<E> child : node.getChildren()) {
            toString(stringBuilder, child, nodeDepth + 1);
        }
    }
}

Demo.java

package net.coderodde.util;

public final class Demo {

    public static void main(String[] args) {
        Tree<Integer> tree = new Tree<>();

        // Roots:
        TreeNode<Integer> root1 = tree.getPseudoRoot().addChild(1);
        TreeNode<Integer> root2 = tree.getPseudoRoot().addChild(2);

        // Children of 1st root:
        TreeNode<Integer> root1Child1 = root1.addChild(11);
        TreeNode<Integer> root1Child2 = root1.addChild(12);

        // Children of 2nd root:
        TreeNode<Integer> root2Child1 = root2.addChild(21);
        TreeNode<Integer> root2Child2 = root2.addChild(22);
        TreeNode<Integer> root2Child3 = root2.addChild(23);

        // Children of 2nd root, second child:
        TreeNode<Integer> root2Child2Child1 = root2Child2.addChild(221);
        TreeNode<Integer> root2Child2Child2 = root2Child2.addChild(222);

        // Print the entire tree in a simple format:
        System.out.println("(Indentation communicates node depth.)");
        System.out.println(new SimpleTreeToStringConverter().toString(tree));
    }
}

Sample output

(Indentation communicates node depth.) 1 11 12 2 21 22 221 222 23

(The project is hosted here. It contains unit tests that pass.)

Critique request

Whatever comes to mind, I would love to hear your suggestions.

Answer 1

Some unordered thoughts:

• The pseudoroot construct violates the law of least surprise (at least for me): from a tree I expect a single root which already contains data. If I need multiple of those, I use a collection of trees.
• Nice idea to encapsulate the child collection in a separate class.
• Why is the Tree final? Someone might want to create a class SomethingTree extends Tree<Something> (note: not me, but someone ;-)). I think, to make a class final you need a specific reason (normally security) and I cannot discern it here.
• Extension suggestion: add an iterator or stream for depth-first and breadth-first traversal (I use these all the time in my own Tree implementation)
• All in all: nicely done

And my personal thanks to you for posting something that is not "programming-challenge" on codereview :-)

Answer 2

TreeNode.java

1) where is equals()
You put child TreeNodes in a Set but did not implement equals(). Even if you meant that TreeNode instances are equal if the references point to the same object, you should state this explicitly and not rely on the default implemetnation in Object - it may change in future (or past) versions of the JRE. As a rule of thumb, equals() should always be explicitly implemented if instances of the class are put in a Collection (any collection as all implement some kind of contains query but especially in a Set that implies concept of uniqeness)

2) null initialized instance variables
I see two problems with this: one is of performance: you are quering if the set is null every time a child is added and every time the view is requested. The second bigger problem is that this code is not thread safe. multiple threads that will try to add the first child to the same node can override each other's operation. The easiest solution is to initialise the children instance variable in TreeNode's constructor.

You were probably trying to implement a lazy initialization DP, but what did you save? creating an empty Set? that is hardly a costly operation both in performance or memory terms.

now, childrenView is a different story. if I understand correctly, this is needed only when a view is requested (i.e. in getChildren()) so why create an instance when a child is added?

TreeNodeChildrenView.java

At first I was buffled as to why you created this feature. I think I understand that you wanted to do some validation checks when a client adds or removes child nodes. However, you already have an addChild() in TreeNode so why not add all other methods there? (you can even have an overloaded version of addChild() that accepts TreeNode arg) seems more natural place to me. Regarding the class itself:

1) add parameterized generic
Insted of implementing Set interface, I would improve on it by adding the missing generics to the methods. instead of contains(Object o) go for contains(TreeeNode<E> node) and let the compiler ensure type safety

2) inner class
TreeNodeChildrenView should be moved to be an inner non-static class of Treenode. IMO - a perfect fit for this case - every instance of the view lives only within the scope of a (non-null!) instance from the enclosing class.