java - Find the smallest non-negative integer not contained in a binary tree -

the method return smallest non-negative integer number not contains in 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 solution o(n^2). how can resolve in time no more 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{         (int i=0;i<a.size();i++){             if (!a.contains(i+1)){                 return i+1;             }         }         return min;     }            } 

you should able calculate number of elements in tree in o(n) walking tree. call value x.

populate boolean array of size x true if index value appears in tree, false otherwise (ie bool[y] == true iff y appears in tree) walking tree. ignore values y in tree y < 0 or y >= x.

the smallest non-negative integer not present in tree either index of first element of boolean array false, or x if elements true.

to put way, container of size x, either:

1. one of numbers 0..x-1 not contained in tree; or
2. all of numbers 0..x-1 contained in tree, in case smallest non-negative number not contained in tree x.