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
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
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.
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 dondod...@gmail.com 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
How come it just reversed the root? I still dont get it!
Rahul
On Feb 9, 7:57 pm, Don dondod...@gmail.com 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
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 menonrahul1...@gmail.com wrote:
How come it just reversed the root? I still dont get it!
Rahul
On Feb 9, 7:57 pm, Don dondod...@gmail.com wrote:
What about just the root being reversed?
Why is it different only in case of root?
Rahul
On Feb 9, 10:52 pm, Don dondod...@gmail.com 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
@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 of
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 srn...@gmail.com wrote:
In binary search,
mid =
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.
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 ankitsamb...@gmail.comwrote:
Here the required program :
void findkthSmallest(Node *root,int k)
{
Node *stack[100];
int top=-1,count=0;
i think sunny's method should work.
On Sat, Jul 30, 2011 at 12:45 PM, varun pahwa varunpahwa2...@gmail.comwrote:
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 ankitsamb...@gmail.comwrote:
Here
would it work
temp=root;
for(int i=0;ik;i++)
{
temp=temp-left;
}
On Jul 29, 10:48 am, sunny agrawal sunny816.i...@gmail.com 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
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 narayan.shiv...@gmail.comwrote:
would it work
temp=root;
for(int i=0;ik;i++)
{
temp=temp-left;
}
On Jul 29, 10:48 am, sunny agrawal sunny816.i...@gmail.com wrote:
Node* x
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
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;
Iterative inorder of tree till you have traversed k elements. Last
element is the kth smallest.
On Jul 29, 10:10 am, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Please tell the solution of this question
Given a Binary Search Tree, write a program to print the kth smallest
element without using
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 ase.as...@gmail.com wrote:
Iterative inorder of tree till you have traversed k elements. Last
element is the kth smallest.
On Jul 29, 10:10 am, AMAN
After expanding B, the border is with G (25)
Node G is the smallest of the border.
You finish the algorithm when the node G is the smallest of the border not
when he enters the boundary
Yes, we finish with G=25, but we still have G=35 first.
This is all right, since I understand now that
a
I have an answer for my own question:
I think I've misunderstood the statement in the book, which says:
...to ensure that the optimal path to any repeated state is always the
first one followed.
in the above example, we haven't actually started to follow (expand) G
yet, so the statement about
Dear Eric,
Initially, we just at the border node S (18).
After expanding the node S, the border is with A (19), B (22).
Node A is the smallest of the border.
After expanding A, the border is with B (22), G (34)
Node B is the smallest of the border.
After expanding B, the border is with G
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
http://en.wikipedia.org/wiki/Skip_list hope it helps :)
On Fri, Mar 11, 2011 at 2:20 PM, kumar vr kumarg...@gmail.com 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
Going by the hint given in the problem
Divide the stream into windows and assume that we have enough space to store
all the queries from the stream window in a hash table along frequency
count. Also maintain a global Hash table that will contain the frequency
counts of top n queries seen so far.
@Srikar
In your first approach you cant simply ignore the queries that are not
present in the heap because you have a stream of queries and you never know
if the query that you are about to ignore is going be received frequently or
not in future. Your approach is like find the top 100 queries
@algoose I see what you are saying. what do you propose? checking out your
link now...
On Thu, Feb 3, 2011 at 11:44 AM, Algoose chase harishp...@gmail.com wrote:
@Srikar
In your first approach you cant simply ignore the queries that are not
present in the heap because you have a stream of
@guy above juver++
The solution , i don't think can get better than this , because you
need to store the querries anyway (at least for the output )
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html
just use words in place of chars...
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Fri, Dec 31, 2010 at 11:00 AM, Davin dkthar...@googlemail.com wrote:
Find the area with less distance between
Find the area with less distance between words. Distance is measured
words count in between two words.
On Dec 30, 4:08 pm, 周翔 csepark...@gmail.com wrote:
Distance is measured on number of words. what is your meaning ? can you
explain it?
2010/12/29 Davin dkthar...@googlemail.com
FindLast(array a, int low,int hi)
{
int mid = (hi - low )/ 2 + 1;
if( a[mid] == City1 a[mid+1] == City2 )
{
return mid;
}
else if ( a[mid] == City1 a[mid+1] == City1 )
{
FindLast(a,mid+1,hi);
}
else
{
FindLast(a,low,mid);
}
}
On Nov 12, 4:39 pm, chitta koushik
sorry
mid = hi+low/2
On Nov 13, 10:52 am, Goose Chase harishp...@gmail.com wrote:
FindLast(array a, int low,int hi)
{
int mid = (hi - low )/ 2 + 1;
if( a[mid] == City1 a[mid+1] == City2 )
{
return mid;
}
else if ( a[mid] == City1 a[mid+1] == City1 )
{
On Nov 13, 4:47 am, Goose Chase harishp...@gmail.com wrote:
sorry
mid = hi+low/2
On Nov 13, 10:52 am, Goose Chase harishp...@gmail.com wrote:
FindLast(array a, int low,int hi)
{
int mid = (hi - low )/ 2 + 1;
I think you mean
mid = (hi + low) / 2;
--
You received this message
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 navka...@gmail.com wrote:
@Prakhar how would you ensure that this is highest index
On Mar 1, 3:05 pm, Prakhar Jain
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 navka...@gmail.com
just fixing a bug
what if you write bin_search as this
//assumption array is in
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 gpsla...@googlemail.comwrote:
of course, you cannot assume that array is in ascending order, it is in
non-decreasing order however
@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 aryansmit3...@gmail.com wrote:
no the order is log(n)
On Wed, Mar 4, 2009 at 4:45 PM, sharad kumar aryansmit3...@gmail.com wrote:
but commplexity is O(n2) rite??wat about my solution??
On Wed, Mar 4, 2009 at 4:32 PM, Prakhar Jain prakh...@gmail.com wrote:
I would call search()
not binsearch()
search() find any index
hmm..
worst case will be O(n).
m not sure but i think avg case would be logn + k ( now if k approx
logn ( kn) where k is the number of times an element can repeat
itself the order remains same)
now if k is large, no of different elements is v low, many times
unsucc search will happen which is
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
cout ((int)((int*)upperbound(a,a+5,k)-a))/4-1;
2009/3/1 sharad kumar aryansmit3...@gmail.com
#includeiostream.h
int main()
{
int a[5]={3,3,3,6,7};
int k;
cink;
int i=0,j=1,c=0;
for(;i5;i++)
{
if(a[j-1]!=a[i] a[i]!=k)
j++;
else
c=i;
}
coutc;
return 0;
}
On Sun, Mar 1, 2009 at
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
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 jaanu.cher...@gmail.com
wrote:
if there are large number of duplicates then it takes long time...
so
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]key)
start=mid;
else
return mid;
}
int
#includeiostream.h
int main()
{
int a[5]={3,3,3,6,7};
int k;
cink;
int i=0,j=1,c=0;
for(;i5;i++)
{
if(a[j-1]!=a[i] a[i]!=k)
j++;
else
c=i;
}
coutc;
return 0;
}
On Sun, Mar 1, 2009 at 9:50 AM, sharad kumar aryansmit3...@gmail.comwrote:
hi,
does the above solution need any time complexity and
Do a binary search in each row or column. If there are m rows and n
columns, this is O(m log n) or O(n log m), respectively.
Dave
On Nov 13, 10:11 am, geekko [EMAIL PROTECTED] wrote:
Given a matrix all whose columns and rows are individually sorted, how
do you search a number in it?
On Nov 13, 11:11 am, geekko [EMAIL PROTECTED] wrote:
Given a matrix all whose columns and rows are individually sorted, how
do you search a number in it?
Of course there are many ways. I assume you want to minimize work.
You can start in the upper right hand corner and go left or down in
46 matches
Mail list logo
