Re: [algogeeks] Re: Binary Search Tree Question

mirror of tree PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@goo

[algogeeks] Re: Binary Search Tree Question

This function is not reversing the tree, it swapping the left and right sub trees. for ex. 6 5 8 4 7 9 1 11 2 => 6 8 5 9 4 111

Re: [algogeeks] Re: Binary Search Tree Question

@Rahul : if you check the flow properly ,(lets concentrate on the root node , call other as left and right subtree) you will find that after done with reversing root->left->left subtree , it reaches root(backtrack to root) node and then swap root->left and root->right. now because it is inorder way

[algogeeks] Re: Binary Search Tree Question

What about just the root being reversed? Why is it different only in case of root? Rahul On Feb 9, 10:52 pm, Don wrote: > Because it reverses one side twice and the other side not at all. > It does a lot of work to accomplish nothing. > Don > > On Feb 9, 9:06 am, Rahul Menon wrote: > > > > > >

[algogeeks] Re: Binary Search Tree Question

Because it reverses one side twice and the other side not at all. It does a lot of work to accomplish nothing. Don On Feb 9, 9:06 am, Rahul Menon wrote: > How come it just reversed the root? I still dont get it! > > Rahul > > On Feb 9, 7:57 pm, Don wrote: > > > > > It appears to be an attempt to

[algogeeks] Re: Binary Search Tree Question

How come it just reversed the root? I still dont get it! Rahul On Feb 9, 7:57 pm, Don wrote: > It appears to be an attempt to reverse the tree. However, there is a > problem. It reverses the left sub-tree, then swaps the left and right > sub-trees. Then it reverses the right sub-tree. But wait!

[algogeeks] Re: Binary Search Tree Question

Thanks! I knew that it wont reverse the tree but was not sure about how it reversed just the root. On Feb 9, 7:57 pm, Don wrote: > It appears to be an attempt to reverse the tree. However, there is a > problem. It reverses the left sub-tree, then swaps the left and right > sub-trees. Then it rev

[algogeeks] Re: Binary Search Tree Question

It appears to be an attempt to reverse the tree. However, there is a problem. It reverses the left sub-tree, then swaps the left and right sub-trees. Then it reverses the right sub-tree. But wait! The original left sub-tree which we reversed is now the right sub-tree, so we actually unreversed it.

[algogeeks] Re: Binary Search Problem

Exactly. And note that if pointers and unsigned integers have the same number of bits, overflow can't be a problem as long as the array elements are 2 bytes or more long. I.e. if you have an n-bit machine, the last 2-byte array element can't have index more than 2^n/2 - 1 = 2^(n-1) - 1. Conseque

[algogeeks] Re: Binary Search Problem

The intermediate value of start+end may be too large to store in an integer, even though start and end by themselves are in the valid range. If you know this to not be the case, you can use the simpler form. Don On Jan 8, 5:04 am, Sanjay Rajpal wrote: > In binary search, > > mid = start + (end-st

Re: [algogeeks] Re: binary search tree question!!!!

i think sunny's method should work. On Sat, Jul 30, 2011 at 12:45 PM, varun pahwa wrote: > do morris traversal until you find k. but that may modify the tree if you > break as you find k. > > > On Sat, Jul 30, 2011 at 9:14 AM, ankit sambyal wrote: > >> Here the required program : >> >> void findk

Re: [algogeeks] Re: binary search tree question!!!!

do morris traversal until you find k. but that may modify the tree if you break as you find k. On Sat, Jul 30, 2011 at 9:14 AM, ankit sambyal wrote: > Here the required program : > > void findkthSmallest(Node *root,int k) > { > Node *stack[100]; > int top=-1,count=0; > Node *temp; >

Re: [algogeeks] Re: binary search tree question!!!!

Here the required program : void findkthSmallest(Node *root,int k) { Node *stack[100]; int top=-1,count=0; Node *temp; stack[++top]=root; /*First we will find the minimum node*/ temp=root; while(temp->left != NULL) { stack[++top]=temp->left; temp->left=

Re: [algogeeks] Re: binary search tree question!!!!

The only way remains is to use the iterative method of traversing a BST in in-order (you have to use a Stack to keep track of father). The place where you print the value of the node, put a condition before that if (!(--k)){ print value_of_node; } in the outermost loop where you check "while(

Re: [algogeeks] Re: binary search tree question!!!!

no it wouldn't try finding a tree where no left exist in the root On Fri, Jul 29, 2011 at 2:14 PM, shiv narayan wrote: > would it work > temp=root; > for(int i=0;i { > temp=temp->left; > } > > On Jul 29, 10:48 am, sunny agrawal wrote: > > Node* x = TREE_MINIMUM(root); > > for(int i = 0; i <

[algogeeks] Re: binary search tree question!!!!

would it work temp=root; for(int i=0;ileft; } On Jul 29, 10:48 am, sunny agrawal wrote: > Node* x = TREE_MINIMUM(root); > for(int i = 0; i < k-1; i++){ > x = TREE-SUCCESSOR(x);} > > return x; > > > > > > > > > > On Fri, Jul 29, 2011 at 11:08 AM, noobcoder wrote: > > Iterative inorder of tree til

Re: [algogeeks] Re: binary search tree question!!!!

Node* x = TREE_MINIMUM(root); for(int i = 0; i < k-1; i++){ x = TREE-SUCCESSOR(x); } return x; On Fri, Jul 29, 2011 at 11:08 AM, noobcoder wrote: > Iterative inorder of tree till you have traversed k elements. Last > element is the kth smallest. > > On Jul 29, 10:10 am, AMAN AGARWAL wrote: > >

[algogeeks] Re: binary search tree question!!!!

Iterative inorder of tree till you have traversed k elements. Last element is the kth smallest. On Jul 29, 10:10 am, AMAN AGARWAL wrote: > Please tell the solution of this question > > Given a Binary Search Tree, write a program to print the kth smallest > element without using any static/global

Re: [algogeeks] Re: binary search for Linked List?

http://en.wikipedia.org/wiki/Skip_list hope it helps :) On Fri, Mar 11, 2011 at 2:20 PM, kumar vr wrote: > We can study about Skip list from wiki or so, > > Assuming that there are no duplicate elements, do we fetch anything > from the skp list? > Priya, > What is the complexity of binary searc

[algogeeks] Re: binary search for Linked List?

We can study about Skip list from wiki or so, Assuming that there are no duplicate elements, do we fetch anything from the skp list? Priya, What is the complexity of binary search on skip list with and without duplicate elements. And in what way it would be better than arrays? The whole questio

[algogeeks] Re: Binary search

Sorry its wrongly posted :( Please Avoid it. Well thanks for suggestion @Miroslav. On Mar 6, 10:19 am, Kapil wrote: > @Prunthaban > In worst case Miroslav's solution also goes for O(n).All elements are > duplicate > But in the case(what i have suggested that i am going to find the > border and

[algogeeks] Re: Binary search

@Prunthaban In worst case Miroslav's solution also goes for O(n).All elements are duplicate But in the case(what i have suggested that i am going to find the border and not the element(key) So the order has to be O(log n) On Mar 4, 5:01 pm, Prunthaban wrote: > @sharad - Your solution is O(n) Mir

[algogeeks] Re: Binary search

the array 2,2,2 is nondecreasing, but is ascending. but the array 1,2,3 is both nondecreasing and ascending I must also point out something that everybody knows, but it is important not to ignore it, mostly on exams. it is that O(log n) is also O(n). So if you say that algorithm complexity is O(n

[algogeeks] Re: Binary search

hmm.. worst case will be O(n). m not sure but i think avg case would be logn + k ( now if k approx logn ( k< wrote: > ya boss rite.but according to asymptotic analysis the solutin shld be > O(n);rite?? > > On Wed, Mar 4, 2009 at 6:48 PM, Prakhar Jain wrote: >> >> see its log(n) + k where k<=t

[algogeeks] Re: Binary search

hmm.. worst case will be O(n). m not sure but i think avg case would be logn + k ( now if k approx logn ( k< wrote: > ya boss rite.but according to asymptotic analysis the solutin shld be > O(n);rite?? > > On Wed, Mar 4, 2009 at 6:48 PM, Prakhar Jain wrote: >> >> see its log(n) + k where k<=t

[algogeeks] Re: Binary search

It is clearly worst case O(n). But Miroslav's solution is proper logn. On Wed, Mar 4, 2009 at 6:48 PM, Prakhar Jain wrote: > > see its log(n) + k where k<=the number of duplicates of the element > being searched. > For log(n), you can continue till your high comes on the element u > desire and

[algogeeks] Re: Binary search

ya boss rite.but according to asymptotic analysis the solutin shld be O(n);rite?? On Wed, Mar 4, 2009 at 6:48 PM, Prakhar Jain wrote: > > see its log(n) + k where k<=the number of duplicates of the element > being searched. > For log(n), you can continue till your high comes on the element u > d

[algogeeks] Re: Binary search

see its log(n) + k where k<=the number of duplicates of the element being searched. For log(n), you can continue till your high comes on the element u desire and not low. On Wed, Mar 4, 2009 at 6:45 PM, sharad kumar wrote: > "search() find any index and then iterates sequentially till the highe

[algogeeks] Re: Binary search

"search() find any index and then iterates sequentially till the highest index" how is this logn On Wed, Mar 4, 2009 at 6:44 PM, sharad kumar wrote: > ya rite > > > On Wed, Mar 4, 2009 at 5:31 PM, Prunthaban wrote: > >> >> @sharad - Your solution is O(n) Miroslav's solution is O(logn). >> An

[algogeeks] Re: Binary search

ya rite On Wed, Mar 4, 2009 at 5:31 PM, Prunthaban wrote: > > @sharad - Your solution is O(n) Miroslav's solution is O(logn). > And what are you doing with the 'j' variable in your solution? Why not > simply use a[i] == k then c = i. That is what eventually your solution > is doing and it is

Re: Fwd: [algogeeks] Re: Binary search

no the order is log(n) On Wed, Mar 4, 2009 at 4:45 PM, sharad kumar wrote: > but commplexity is O(n2) rite??wat about my solution?? > > On Wed, Mar 4, 2009 at 4:32 PM, Prakhar Jain wrote: >> >> I would call search() >> not binsearch() >> search() find any index and then iterates sequentially t

[algogeeks] Re: Binary search

@sharad - Your solution is O(n) Miroslav's solution is O(logn). And what are you doing with the 'j' variable in your solution? Why not simply use a[i] == k then c = i. That is what eventually your solution is doing and it is O(n). On Mar 4, 4:32 pm, sharad kumar wrote: > pls tell wats differen

[algogeeks] Re: Binary search

pls tell wats difference btwn increasing and non decresing sorted array.question clearly tells n sorted array... On Wed, Mar 4, 2009 at 4:55 PM, Miroslav Balaz wrote: > of course, you cannot assume that array is in ascending order, it is in > non-decreasing order however not in ascending > an

[algogeeks] Re: Binary search

of course, you cannot assume that array is in ascending order, it is in non-decreasing order however not in ascending and you should swap order here :(a[mid+1] > key||mid==high) 2009/3/4 Kapil > > just fixing a bug > > what if you write bin_search as this > //assumption array is in ascending ord

Re: Fwd: [algogeeks] Re: Binary search

but commplexity is O(n2) rite??wat about my solution?? On Wed, Mar 4, 2009 at 4:32 PM, Prakhar Jain wrote: > > I would call search() > not binsearch() > search() find any index and then iterates sequentially till the highest > index. > > Prakhar > > On Wed, Mar 4, 2009 at 4:27 PM, Kapil wrote:

Re: Fwd: [algogeeks] Re: Binary search

I would call search() not binsearch() search() find any index and then iterates sequentially till the highest index. Prakhar On Wed, Mar 4, 2009 at 4:27 PM, Kapil wrote: > > @Prakhar how would you ensure that this is highest index > > On Mar 1, 3:05 pm, Prakhar Jain wrote: >> I guess the Soln

Re: Fwd: [algogeeks] Re: Binary search

@Prakhar how would you ensure that this is highest index On Mar 1, 3:05 pm, Prakhar Jain wrote: > I guess the Soln given is O(n) > Much better can be achieved through binary serach O(nlogn) > > int binsearch(int a[],int start,int end,int key) > { > int mid=(start+end)/2; > if(start==end && a[mid

[algogeeks] Re: Binary search

just fixing a bug what if you write bin_search as this //assumption array is in ascending order binsearch(high, low, key, a) begin if low > high return -1 mid = (high+low)/2 if a[mid] = key And (a[mid+1] > key||mid==high) return mid if a[mid] <= key low = mid+1 else high = mid -

[algogeeks] Re: Binary search

what if you write bin_search as this //assumption array is in ascending order binsearch(high, low, key, a) begin if low > high return -1 mid = (high+low)/2 if a[mid] = key And a[mid+1] > key return mid if a[mid] <= key low = mid+1 else high = mid - 1 return binsearch(high,low,key

[algogeeks] Re: Binary search

YES, you only need good invariant, initialy you put end=n to point outside the array and start=0 to point on the first element invariant is that start points to candidate solution, and that end points to element that cant be considered an answer if you calculate mid=(start+end)/2, then it will nev

[algogeeks] Re: Binary search

c i tested it for all possibilities.it gives the largest index for particular duplicate at both extreme boundaries.o(nlogn is a bit slow... On Sun, Mar 1, 2009 at 4:44 PM, CHERUVU JAANU REDDY wrote: > if there are large number of duplicates then it takes long time... > so we have to apply Binary

[algogeeks] Re: Binary search

if there are large number of duplicates then it takes long time... so we have to apply Binary search on rightside. On Sun, Mar 1, 2009 at 3:35 PM, Prakhar Jain wrote: > > I guess the Soln given is O(n) > Much better can be achieved through binary serach O(nlogn) > > int binsearch(int a[],int sta

Fwd: [algogeeks] Re: Binary search

I guess the Soln given is O(n) Much better can be achieved through binary serach O(nlogn) int binsearch(int a[],int start,int end,int key) { int mid=(start+end)/2; if(start==end && a[mid]!=key) return -1; if(a[mid]>key) end=mid; else if(a[mid]=0) while(a[p]==key) p++; return p-

[algogeeks] Re: Binary search

cout << ((int)((int*)upperbound(a,a+5,k)-a))/4-1; 2009/3/1 sharad kumar > #include > int main() > { > int a[5]={3,3,3,6,7}; > int k; > cin>>k; > int i=0,j=1,c=0; > for(;i<5;i++) > { > if(a[j-1]!=a[i]&& a[i]!=k) > j++; > else > c=i; > } > cout< return 0; > > } > > On Sun, Mar 1, 2009 at 9:50 AM,

[algogeeks] Re: Binary search

#include int main() { int a[5]={3,3,3,6,7}; int k; cin>>k; int i=0,j=1,c=0; for(;i<5;i++) { if(a[j-1]!=a[i]&& a[i]!=k) j++; else c=i; } cout > hi, > does the above solution need any time complexity and space complexity in > specifific. idont understand use binary search > > On Sun, Mar 1,

[algogeeks] Re: Binary search

hi, does the above solution need any time complexity and space complexity in specifific. idont understand use binary search On Sun, Mar 1, 2009 at 12:13 AM, jaanu wrote: > > Given a sorted arrays of N integers, possibly with duplicates, write a > function that > returns the highest index of an el