First do a level order traversal.Let the result of level order traversal be
stored in a list l (List<Tree> l = new ArrayList<Tree>).
Then we can do similar to level order once again.There will be two loops.
Outer loop will take an element from list l and treat it as root and the
inner loop will do
lever order traversal on this root.
Now check the data of left and right child of root with root data and
accordingly increment the length
of BST traversed so far.Compare this length with a max value and accordingly
update the max value.
Finally return max value.
Something like below.
int len =0;
int i=0;
int size = l.size();
int tempLen =0;
for(i=0;i<size;i++){
Queue<Integer> q = new LinkedList<Integer>();
q.add(i);
tempLen =1;
while(!q.isEmpty()){
int j = q.poll();
if(2*j+1 < size){
if(l.get(2*j+1).data<l.get(j).data){
tempLen++;
q.add(2*j+1);
}
}if(2*j+2 < size){
if(l.get(2*j+2).data>= l.get(j).data){
tempLen++;
q.add(2*j+2);
}
}
}
if(tempLen>len){
len = tempLen;
}
}
return len;
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
