Max depth of tree when all parent pointers are provided Request for optimization, good practices, recommendations.

class NodeMaxDepth {

    private final NodeMaxDepth parent;

    public NodeMaxDepth (NodeMaxDepth parent) {
        this.parent = parent;
    }

    public NodeMaxDepth getParent() {
        return parent;
    }
}


    /**
     * Given a list of nodes with parent pointers, 
     * calculate the max depth of tree from the root.
     */
    public final class MaxDepth {

        private MaxDepth ( ) { }

        public static int maxDepth (List&lt;NodeMaxDepth&gt; nodes) {
            if (nodes.size() == 0) { throw new IllegalArgumentException("List of nodes is empty."); }

            final Map&lt;NodeMaxDepth, List&lt;NodeMaxDepth&gt;&gt; parentChild = new HashMap&lt;NodeMaxDepth, List&lt;NodeMaxDepth&gt;&gt;();
            NodeMaxDepth parent = null;

            for (NodeMaxDepth node : nodes) {
                if (node.getParent() == null) parent = node; 

                if (!parentChild.containsKey(node.getParent())) {
                    List&lt;NodeMaxDepth&gt; count = new ArrayList&lt;NodeMaxDepth&gt;();
                    parentChild.put(node.getParent(), count);
                }
                parentChild.get(node.getParent()).add(node);
            }

            if (parent == null) {
                throw new IllegalArgumentException("The graph should be acyclic.");
            }

            return height (parentChild, parent);
        }



        private static int height (Map&lt;NodeMaxDepth, List&lt;NodeMaxDepth&gt;&gt; parentChild, NodeMaxDepth parent) {
            assert parentChild != null;
            assert parent != null;

            final List&lt;NodeMaxDepth&gt; childList = parentChild.get(parent);

            if (childList == null) return 0;

            int maxCount = 0;
            for (NodeMaxDepth child : childList) {
                int height = height(parentChild, child);
                if (height &gt; maxCount) {
                    maxCount = height;
                }
            }
            return maxCount + 1;
        }


        public static void main(String[] args) {
            NodeMaxDepth root = new NodeMaxDepth(null);
            NodeMaxDepth nodeLeft = new NodeMaxDepth(root);

            NodeMaxDepth nodeRight = new NodeMaxDepth(root);
            NodeMaxDepth nodeRightRight = new NodeMaxDepth(nodeRight);
            NodeMaxDepth nodeRightRightRight = new NodeMaxDepth(nodeRightRight);

            List&lt;NodeMaxDepth&gt; nodes = new ArrayList&lt;NodeMaxDepth&gt;();
            nodes.add(root);
            nodes.add(nodeLeft);
            nodes.add(nodeRight);
            nodes.add(nodeRightRight);
            nodes.add(nodeRightRightRight);

            System.out.println("Expected 3, Actual: " + maxDepth (nodes));
        }
    }
You shouldn't name your classes which form the data structure you operate on according to the problem you are trying to solve. The classes should be named according to their function in the data structure. Thus NodeMaxDepth should be simply Node. This also removes visual clutter when reading the code as the name is shorter yet conveys the same meaning.
I'm not 100% sure why you build the list of children for each node in a separate data structure - it seems that this should be part of the NodeMaxDepth class. It would also make for a slightly cleaner implementation of building of the children lists as each node only has to add itself to the children collection of its parent.

Something along these lines:

class Node {

    private final Node parent;
    private List&lt;Node&gt; children;

    public Node(Node parent) {
        this.parent = parent;
        children = new List&lt;Node&gt;();
    }

    public Node getParent() {
        return parent;
    }

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


public static int maxDepth(List&lt;Node&gt; nodes) {
    if (nodes.size() == 0) { throw new IllegalArgumentException("List of nodes is empty."); }

    Node root = null;

    for (Node node : nodes) {
        if (node.getParent() == null) {
            if (root != null) {
                throw new IllegalArgumentException("Tree must not have multiple roots");
            }
            root = node; 
        }
        else {
            node.getParent().addChild(node);
        }
    }

    if (root == null) {
        throw new IllegalArgumentException("This does not seem to be a tree");
    }

    return height (root);
}

If you want to optimize for memory usage and code size you could resort to a simpler algorithm by simply walking up the tree from each node to the root and remember the longest path. Worst case this would result in O(n^2) runtime if I'm not mistaken but would not require any additional memory for building the children lists. The code would also be much simpler.

As indicated by @200_success you could sacrifice a little bit more memory and find all leave nodes and just walk up from them:

// assume all nodes are leaves
HashSet&lt;Node&gt; leaves = new HashSet&lt;Node&gt;(nodes);

Node root = null;

// remove all parents as they are not leaves
for (Node node : nodes) {
    if (node.getParent() == null) { 
        root = node;
    }
    else {
        leaves.remove(node.getParent());
    }
}

if (root == null) {
    throw new IllegalArgumentException("The tree must have a root");
}

int maxHeight = 0;

for (Node leaf : leaves) {
    int height = 1;
    Node current = leaf;
    while (current.getParent() != null) {
        current = current.getParent();
        height += 1;
    }
    if (maxHeight &lt; height) {
        maxHeight = height;
    }
}

return maxHeight;

You don't really check for cycles - just that your tree has a root (you could have a normal tree and a disconnected cycle in the list).