as a hint, convert the BST to a sorted array and take two pointers one pointing to the first number and the other pointing to the last. Then, move pointers appropriately to find the two numbers summing up to k.
complexity: O(n) 2010/8/5 Seçkin Can Şahin <[email protected]> > what about the case: > array : 1 3 10 100 and k = 101. Your code doesn't find it I suppose. > > > On Thu, Aug 5, 2010 at 11:15 PM, Avik Mitra <[email protected]> wrote: > >> >> Inorder traversal of the BST will give elements in sorted way. Let us >> assume that the sorted elements are in an array A of length N. >> set i=1; >> while i <N-1 >> { >> if a[i] > k, then output: "No such node" >> else if(a[i]==k) >> { >> if (a[i+1] ==0) >> output: "Two nodes found" BREAK; >> else >> output: "No such node." BREAK. >> >> } >> >> else if(a[i] <k ) >> { >> if(a[i]+a[i+1]==k) >> output: "Two nodes found" BREAK. >> else if(a[i]+a[i+1] >k) >> output: "No such node" BREAK >> else if(a[i] +a[i+1] < k) >> i++ ; >> } >> }//End of while-loop. >> >> -- >> 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]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- 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.
