have a look http://amnwidfrenz-thinkalways.blogspot.in/2012/09/string-
reduction.html
--
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
10
4 5
2 7 6 11
1 39 8 12 13 14 15
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
the first cousins are 9,8 not 12,13...otherwise the question becomes
really simple :)
Best Regards
bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[]
path, int pos, vectorint firstCousins)
{
if ((!pThis) || (!pRoot)) return false;
if (pRoot-data!=pThis-data) {
path[pos] = pRoot;
if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins))
return
Shouldn't having 2 queues one storing the node and other corresponding
level should be sufficient and do level order traversal?
-mithun
On Mon, May 21, 2012 at 5:54 PM, Ashish Goel ashg...@gmail.com wrote:
bool firstCousins(struct node * pRoot, struct node *pThis, (struct
node*)[] path,
//considering node who's cousins need to be find as start..
node * a[10];
while(root!=start)
{
a[i]=root;
i++;
if(root-data start-data)
root=root-left;
else
root=root-right;
}//we can do this using recursion
node *grand=a[i-2];
if(start-data grand-data)
I think this works and the complexity is O(sqrt(n))
#includecmath
#includecstdio
#includeiostream
#includecstring
#includecstdlib
using namespace std;
# define INFY 17
int main()
{
int n, i, j;
int val, minDiv, minDis;
while(1)
{
cin n;
minDis =
+1 @ anurag's solution.agree with O(sqrt(n)) complexity.
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
seems like quesion of permutation, it will take all the permutation to
check which one can lead to answer, there will be always be more than
one solution
complexity ((n-1)!)
anyone for better solution ??
On Nov 12, 4:27 pm, surender sanke surend...@gmail.com wrote:
@myself
if number of
The Complexity of my solution is of Order n . At most I Traverse the whole
string twice ..
On Sat, Nov 12, 2011 at 8:29 PM, vikas vikas.rastogi2...@gmail.com wrote:
seems like quesion of permutation, it will take all the permutation to
check which one can lead to answer, there will be always
Well it aint O(n) ..:P ...The erase part will be complex and will take
shifting string parts . So complexity will be O(n^2) for str.erase operation
On Sat, Nov 12, 2011 at 8:34 PM, Ankur Garg ankurga...@gmail.com wrote:
The Complexity of my solution is of Order n . At most I Traverse the
@sagar for one time u r taking the return value of newly created
process and for other time u r taking return value of parentir it
right??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
But the o/p at
http://ideone.com/zKZuS
seems to be different than what one is getting from parent child tree
On Aug 8, 10:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
instead of that find sum of first n natural number sum ie (n(n+1))/2.;say
NSum
then find the sum of all elements of the array . say ASum
ASUm - NSum = result (no repeated twice).
On Fri, Aug 19, 2011 at 7:30 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote:
:)
*Regards
Sanju
Happy to Help
Hi folks,
I just thought since the range of the numbers is not known so can go
this way;
1.We can find the max number in the array in o(n)=MAX say
2.Then (MAX(MAX+1))/2-sum(a[1n]) of given
array=S=(a1+a2+.+an)-R
3.
But let us think in more general case let us say that numbers are
1 4 77 88 90 88
Then How to do it???
On Fri, Aug 19, 2011 at 5:01 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote:
Yes this is the restriction and in assumption I have cleared it .
*Regards
Sanju
Happy to Help :)*
Sorting can be used i.e. O(nlogn).
Since O(1) space constraint is there, so hashing can't be used.
*Regards
Sanju
Happy to Help :)*
On Fri, Aug 19, 2011 at 4:36 AM, monty 1987 1986mo...@gmail.com wrote:
But let us think in more general case let us say that numbers are
1 4 77 88 90 88
@sanjay: Why doesn't your algo work if the nos are not in the range 1-n??
--
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
acc to your logic,
it should be 1^2^3^4^5^5^6
which is 1^2^3^4^6 (5^5 is zero)
now when you XOR this with the given array,
the result will again be 0.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
You did not get my point, second time you have to XOR with Natural numbers,
not with original array.
Check out my post again :)
After u calculated 1^2^3^4^6,let this be Res.
XOR this result with Res^1^2^3^4^5^6.
Now you got the point ?
*Regards
Sanju
Happy to Help :)*
On Fri, Aug 19, 2011
Oh yes yes i got it now!! I missed that point!
--
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
:)
*Regards
Sanju
Happy to Help :)*
--
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...@googlegroups.com.
For
bitset would work i guess
On Aug 18, 7:10 pm, hary rathor harry.rat...@gmail.com wrote:
bitset is best . require only 32 time less then require in hash table .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email
use (dynamic/ infinite)array initial the array with -1.
insert(int a)
{
array[a]=a;
}
delete(int a)
{
array[a]=-1;
}
..
Thank you,
Siddharam
On Thu, Aug 18, 2011 at 7:54 PM, DheerajSharma
dheerajsharma1...@gmail.comwrote:
bitset would work i guess
On Aug 18, 7:10 pm, hary rathor
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr=
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy`
only once
On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh saurab...@gmail.com wrote:
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as
O(1) space means constant space. It doesn't mean you can't use extra space.
Refer here:
http://stackoverflow.com/questions/2219109/what-does-this-mean-on-steps-and-o1-space
According to the question you can definitely use a Hash Table for keeping
hit record, as it will be a constant space
true. I agree , we can use additional memory which will be constant
irrespective of counjt of elements.
But using an hash wont be a constant memory as input can keep on varying.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 8:16 AM, Dipankar Patro dip10c...@gmail.com wrote:
O(1) space means constant
hash map is the solution provided the elements lie in a predefined range..
On Fri, Aug 19, 2011 at 8:46 AM, *$* gopi.komand...@gmail.com wrote:
true. I agree , we can use additional memory which will be constant
irrespective of counjt of elements.
But using an hash wont be a constant memory
yes , but that constraint is not provided by the interviewer , hence ,
solution of hash is not acceptable
On Fri, Aug 19, 2011 at 8:58 AM, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
hash map is the solution provided the elements lie in a predefined range..
On Fri, Aug 19, 2011 at 8:46
In the first loop, numbers are the numbers in the given array
but in the second loop, numbers are just natural numbers.
I forgot to mention as people may get confused.
*Regards
Sanju
Happy to Help :)*
--
You received this message because you are subscribed to the Google Groups
Algorithm
@Dave
How is the complexity O(n^2logn) .. Can you please tell
I believe there cant be solution better than O(n^2) unless u use FFT which
again is out of scope , at least for me :)
Regards
Ankur
2011/8/11 Samba Ganapavarapu sambasiv...@gmail.com
Can we find any alg. which runs faster than
Can we find any alg. which runs faster than O(n^2) using these 2 axioms ?
2011/8/10 Amethy hobby news...@gmail.com
it also like Pythagorean theorem;
so the a[k] also with the value where
a[j]-a[i]a[k]a[i]+a[j]
and a[k]a[j]=a[i];
On 8月9日, 下午10时43分, Samba Ganapavarapu sambasiv...@gmail.com
@Ankit Sambyal: Agree with ankuj...TC of your solution is O(nlogn) and not
O(n^2)...
--
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
@kunal, anuj : step 2 of my algo takes O(n^2). So how can the TC be O(nlogn)
--
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
@Ankit: Ohh Sorry..I didnt actually read the question properly..
I didnt see we have to check for sum which must be another element in the
array not some user provided constant value..I mis-understood it with sum
upto k problem which can be solved on sorted array in O(n)...
thats why gave a wrong
After squaring all the elements up and sorting them, couldn't we just do a
binary search on the array.. so the TC would be O(nlogn)...
On Wed, Aug 10, 2011 at 1:18 PM, Kunal Patil kp101...@gmail.com wrote:
@Ankit: Ohh Sorry..I didnt actually read the question properly..
I didnt see we have to
@Dinoja: No. You can only binary search for 1 thing, so you would have
to choose two elements and then search for the third. Thus, the order
would be O(n^2 log n).
Dave
On Aug 10, 6:11 pm, Dinoja Padmanabhan dino...@gmail.com wrote:
After squaring all the elements up and sorting them, couldn't
it also like Pythagorean theorem;
so the a[k] also with the value where
a[j]-a[i]a[k]a[i]+a[j]
and a[k]a[j]=a[i];
On 8月9日, 下午10时43分, Samba Ganapavarapu sambasiv...@gmail.com wrote:
We have an array of integers, we need to find the element a[i],a[j] and a[k]
values where.. a[i]^2 + a[k]^2 = a[k]
How is the time O(n^2).It is O(nlgn)
On Aug 9, 7:53 pm, ankit sambyal ankitsamb...@gmail.com wrote:
1. Square each element of the array and then sort it---O(nlogn)
2. for(i=0;i(size-3);i++)
{
j=i+1; k=size-1;
while(jk)
{
if(a[[i] + a[j] == a[k])
can anyone explain how it's working i didn't get it???
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.com wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii
When Process executed fork(). It create the Same Structure as the main
process.The only difference is the return value of the child fork process is
0 and that of parent is the PID of its Child process.
Now you can draw the pictorial representation of the fork processes during
the execution and
At the point of execution of the 4th fork(), there are 8 processes i.e, the
4th fork will get executed 8 times. The final value of ret will depend on
this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.com wrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and rest
0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal kamakshi...@gmail.comwrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.comwrote:
lets label your forks :-
M
/ \
/\
/\
/ \
/ \
/ \
/ \
i was asking about the order in printfso it wud be like 8times one and
then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.com wrote:
M
/ \
/\
/\
/ \
/
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg aditi.garg.6...@gmail.comwrote:
i was asking about the order in printfso it wud be like 8times one and
then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek
@aditi
nope... it will run in parallel...so order is not fix
On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra pradam.prad...@gmail.comwrote:
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg aditi.garg.6...@gmail.comwrote:
i was asking
@sagar thanx :)
On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek sagarpar...@gmail.com wrote:
@aditi
nope... it will run in parallel...so order is not fix
On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra
pradam.prad...@gmail.comwrote:
no it'll vary as the PID will vary from parent to
@sagar: i think order has to be fixed...in amazon they gave us four
options
but i dnt remember them now...
On Mon, Aug 8, 2011 at 10:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@sagar thanx :)
On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek sagarpar...@gmail.comwrote:
@aditi
@kamaskshi:
The order of execution of the processes cant be in user hands.It is a
scheduling aspect.So we cant expect the peculiar order.
On 8 August 2011 22:10, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@sagar: i think order has to be fixed...in amazon they gave us four
options
but
the order of printfs depend on the scheduling algorithms which OS is
following and can't be predicted
--
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
@ankit:i feel you are right!!!
Thank you,
Siddharam
On Mon, Aug 8, 2011 at 10:56 PM, ankit sambyal ankitsamb...@gmail.comwrote:
the order of printfs depend on the scheduling algorithms which OS is
following and can't be predicted
--
You received this message because you are subscribed to
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order appending
the node found on the way.
total complexity would be O(construction of suffix tree ) +
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM, surender sanke surend...@gmail.com wrote:
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh saurab...@gmail.com wrote:
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM,
The following code can be used to generate permutations of the string.. but
still some bugs are there like to avoid already printed char etc.. however
logic will be similar..
order will be less that n^2
// stringPermutration.cpp : Defines the entry point for the console
application.
//
#include
http://en.wikipedia.org/wiki/Substring
ac should be a subsequence and not substring.
On Jul 28, 12:00 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh saurab...@gmail.com wrote:
#include cstdio
#include cstring
using namespace std;
const int MX = 1000;
char str[MX], sol[MX];
bool seen[MX] = {0};
void print(int n, int k=0) {
if(k==n) {
sol[n] = 0; printf(%s\n, sol);
return;
}
for(int i = 0; i n; i++) {
if(!seen[i]) {
suffix tree can be used print all the nodes...u ll get every
substring ..!!
On Jul 26, 8:51 pm, Ankur Garg ankurga...@gmail.com wrote:
Hey Guys
Can we use KMP Algorithm here to generate permutations...May be a bit
modification is req
On Tue, Jul 26, 2011 at 9:07 PM, keyan karthi
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
You received this message because you are subscribed to the Google Groups
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and
using suffix tree this can be done in o(nlogn) though will take extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.comwrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit
This essentially becomes a two pass algo
first find the parent and grand parent and find children of all the
siblings of the parent
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com
@Priya: Assuming that cousins means first cousins, then cousins
have a common grandparent but different parents. Other people on the
same level would not be first cousins.
The algorithm is to go up two levels (to the grandparent) and descend
to the other child (to an aunt or uncle). The children
@Dave i understood it thanks :)
On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote:
@Priya: Assuming that cousins means first cousins, then cousins
have a common grandparent but different parents. Other people on the
same level would not be first cousins.
The algorithm is
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
he already pointed out that there are no repetations..!!
On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal vipin.iitr@gmail.comwrote:
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as
@Gunjani made a mistake...u r right...but there is one more hidden
assumption that the numbers are positive integers.
On Thu, Mar 3, 2011 at 10:57 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
he already pointed out that there are no repetations..!!
On Thu, Mar 3, 2011 at 9:40 PM,
And Integers too :P
On Fri, Mar 4, 2011 at 12:03 AM, nishaanth nishaant...@gmail.com wrote:
@Gunjani made a mistake...u r right...but there is one more hidden
assumption that the numbers are positive integers.
On Thu, Mar 3, 2011 at 10:57 PM, sukhmeet singh
@jalaj dude..its not d problem u can convert string ti tree easily
First Check Out Solution i have posted
Thank Regards
Shashank Mani The best way to escape from a problem is to solve
it
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
can u explain what is meant by binary tree as a mirror strucrure ?
is it like all left and right subtrees in tree should be mirror image
of each other..
if that is the case then (A (B (C)), D(E))) should be (A (B (C)),
D(,E)))
means if C is the left child of B then E should be the right child of
Correct representation of tree in string format is
(root Left sub tree,right sub tree)
and if Left sub tree is NULL then it is (root,right sub tree) so as
differentiate b/w case
1. when B is left child of A (A (B))
2. or B is right child of A(A,(B))
On Feb 6, 3:34 pm, jalaj jaiswal
hi,
I think we can use a stack here...
start from left of string(0 to n)
till we don't get a ')' we will keep on pushin the elements on the
stack...
if we encounter a '0' we will pop elements till ')' if this count is 2
everytime except the last time then this is a mirror tree else
@jalal hi You Can Use This algorithm to construct the Mirror tree
(1) Call Mirror for left-subtreei.e., Mirror(left-subtree)
(2) Call Mirror for right-subtree i.e., Mirror(left-subtree)
(3) Swap left and right subtrees.
temp = left-subtree
left-subtree = right-subtree
Here is working Code
//code is very simple from understanding points of view
//we can solved the problem dynamically or more efficiently but i
posted the solution by taking every things statically ..but its
working what question asked.for
#includestdio.h
#includeconio.h
int main()
{
int
Looks good. I concede that it works for a Binary Search Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.com wrote:
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not
Yes,it works for binary search tree only
On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard nphard.nph...@gmail.comwrote:
Looks good. I concede that it works for a Binary Search Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard,see the following approach
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not NULL)
{
/*Determine if Q is node's right child or successor*/
/*Q is inorder successor of node*/
IF (Q-left == node OR
solution is not too hard to understand!!
1. [quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
last node in left sub tree of any
@Ritu - Do you realize that you cannot just convert a given binary tree into
right-threaded binary tree? You need at least 1 bit information at each node
to specify whether the right pointer of that node is a regular pointer or
pointer to the inorder successor. This is because traversal is done
this is a tree traversal(depth first) problem.
as for the extra space, depends on how you see it. fifth can be the
counter and when the counter reaches 0, you have your fifth largest
element
On Jan 21, 9:58 am, nagaraj N nagaraj1...@gmail.com wrote:
How do you find out the fifth maximum element
@nphard
ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that there ll be no further insertions taking
place in tree and no other traversal is required.
here we suppose
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
it can be done in O(n) time using right threaded binary tree.
1.Convert the tree to right threaded tree.
right threaded tree means every node points to its successor in
tree.if right child is not NULL,then it already contains a pointer to
its successor Else it needs to filled up as following
it can be done in O(n) time using right threaded binary tree.
1.Convert the tree to right threaded tree.
right threaded tree means every node points to its successor in
tree.if right child is not NULL,then it already contains a pointer to
its successor Else it needs to filled up as following
If you convert the given binary tree into right threaded binary tree, won't
you be using extra space while doing so? Either the given tree should
already be right-threaded (or with parent pointers at each node) or internal
stack should be allowed for recursion but no extra space usage apart from
No,no extra space is needed.
Right children which are NULL pointers are replaced with pointer to
successor.
On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote:
If you convert the given binary tree into right threaded binary tree, won't
you be using extra space while doing so?
1 - 100 of 153 matches
Mail list logo
