Hi guys,
I believe the definition of exterior is incorrect. You define it as a path from the root to the leftmost leaf (leaf that appears first in an inorder traversal).
If we run your solution on a modified tree where node B(6) has no left child, the answer would be A,B,F,G,H,…
But nodes F,G are
- not leaves
- they are not on the path from root to the leftmost element which is B(6)
The same holds for the right border: if we remove right child of I(6), nodes J and K become part of the answer.
So, I guess you need to change the formulation of the problem.
In addition, using addAll() on a LinkedList has O(n) running time and probably should be replaced by passing LinkedList as an argument to recursive call.
I came up with an (easier?) solution which does a single traversal and uses 2 variables for left and right borders:
public static <T> List<T> computeExterior(TreeNode<T> root) {
List<T> exterior = new ArrayList<>();
computeExterior(root, exterior, true, true);
return exterior;
}
private static <T> void computeExterior(TreeNode<T> node, List<T> exterior, boolean left, boolean right) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
exterior.add(node.data);
return;
}
if (left) {
exterior.add(node.data);
}
computeExterior(node.left, exterior, left, node.right == null ? right : false);
computeExterior(node.right, exterior, node.left == null ? left : false, right);
if (right && !left) {
exterior.add(node.data);
}
}
We pass information to the child if it’s a left/right border. If node has no left/right child, then its right/left child become the border.
It’s a mixture of inorder traversal for left border and postorder traversal for right border (because we need right elements from bottom to top).