Find all nodes on the path of the diameter of a binary tree

Please refer to the post here: http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

The diameter of a binary tree is the maximum length of the path between any nodes in a binary tree. So the problem is to find the diameter then print out all of the nodes on the path of diameter. Note there could be multiple diameters, but we just need to print out one path.

The key is to most of the tree problem is using dynamic programming to construct solution based on the children of the current node. That is: solution(current) = fn(solution(left), solution(right)). The key is to construct the solution.

Note the current tree diameter can be computed as maximum of the following three values:
1. longest path from leaves to left node + longest path from leaves to right node
2. diameter of left subtree
3. diameter of right subtree.

public static class DiaData{

//the nodes on the longest path from children to current node

List<Node> maxPath;

//the nodes on the diameter path with current node as root

List<Node> diameter;

DiaData(List<Node> path, List<Node> dia){this.maxPath = path; this.diameter = dia;}

}

public static List<Node> findNodesOnTreeDiameter(Node tree){

DiaData  re = findNodesOnTreeDiameterUtil(tree);

return re.diameter;

}

public static DiaData findNodesOnTreeDiameterUtil(Node tree){

if(tree==null){

return new DiaData(Collections.EMPTY_LIST, Collections.EMPTY_LIST);

DiaData left = findNodesOnTreeDiameterUtil(tree.left);

DiaData right = findNodesOnTreeDiameterUtil(tree.right);

int leftMaxPsize = left.maxPath.size();

int rightMaxPSize = right.maxPath.size();

int leftMaxSubSize = left.diameter.size();

int rightMaxSubSize = right.diameter.size();

int maxSubSize = Math.max(leftMaxPsize+rightMaxPSize+1, Math.max(leftMaxSubSize, rightMaxSubSize));

//list of nodes on the diameter for the subtree rooted at current node: tree

List<Node> diameter = new ArrayList<Node>();

if(leftMaxSubSize == maxSubSize)

diameter = left.diameter;

else if(rightMaxSubSize == maxSubSize)

diameter = right.diameter;

else{

diameter.addAll(left.maxPath); 

diameter.add(tree);

diameter.addAll(right.maxPath);

}

//list nodes on the longest path from leaf to current node: tree

List<Node> maxPath = new ArrayList<Node>(); 

if(leftMaxPsize>rightMaxPSize)

maxPath.addAll(left.maxPath);

else

maxPath.addAll(right.maxPath);

maxPath.add(tree);

return new DiaData(maxPath, diameter);

}