Given a problem:
find diameter of binary tree (diameter is longest possible path between any two nodes in a tree)
Node format:
public class TreeNode {
TreeNode left;
TreeNode right;
}
External variable approach:
int maxDiameter = 0; //we will update this external variable from recursion calls
public int diameterOfBinaryTree(TreeNode root) {
explore(root);
return maxDiameter;
}
public int explore(TreeNode node) {
if (node == null) {
return 0;
}
int left = explore(node.left);
int right = explore(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return Math.max(left, right) + 1;
}
Composite return approach:
To solve this task in clear functional way, without external variables, need to return information about max diameter found instead of updating a variable. As now it's needed to return 2 values (max diameter found and depth), will simply return int[]
.
public int diameterOfBinaryTree(TreeNode root) {
return explore(root)[1];
}
public int[] explore(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] left = explore(node.left);
int[] right = explore(node.right);
int maxDepth = Math.max(left[0], right[0]);
int maxDiameter = Math.max(Math.max(left[1], right[1]), left[0] + right[0]);
return new int[]{maxDepth + 1, maxDiameter};
}
Which approach do you prefer?
From my point of view, if mutability is acceptable, external variable is the way to go.