find the smallest non-negative integer value which is not present in the subtree of that node"
Answers
Explanation:
the method return the smallest non-negative integer number that is not contains in the binary tree.
Example:
with 0 1 2 3 return 4.
with 1 2 3 4 return 0.
with 0 1 2 5 6 return 3.
with 6 1 5 2 return 3.
Complexity of my solution is O(n^2). How I can resolve in a time no more than O(n)?
public static <E> int minIntNotContains(BinTree<Nodo<Integer>> node) {
List<Integer> a=new ArrayList<Integer>();
int min=minIntNotContainsRic(node,a);
return min;
}
public static <E> int minIntNotContainsRic(BinTree<Nodo<Integer>> node,List<Integer> a) {
int min= node.getValue().getValue();
a.add(node.getValue().getValue());
if(node.getLeftSubtree() != null) {
min = Math.min(min, minIntNotContainsRic(node.getLeftSubtree(),a));
}
if(node.getRightSubtree() != null) {
min = Math.min(min, minIntNotContainsRic(node.getRightSubtree(),a));
}
if (min>0) return 0;
else{
for (int i=0;i<a.size();i++){
if (!a.contains(i+1)){
return i+1;
}
}
return min;