[algogeeks] Building a Binary tree with XOR
Hi All,
Before starting any binary tree problem I will be creating such kind
of binary tree and will be solving that problem accordingly.
From the last few days I am trying to code to build a binary tree with
Exclusive Operators. Here I am trying to build the tree in the level
order way like all the elements will be placed in the queue in the
order of levels so that the final binary tree will be almost complete
binary tree.
In general the left node will contain the left side tree adress
details and right node will contain the right tree details.
But the XOR Binary trees will be holding the XOR values of parent and
left child in the left node and in the same way the parent and right
child will be in the right part.
Here I am unable to track the parent of a particular node after the
level 3. Does it possible to create a XOR binary tree with the level
order mechanism. If possible, could you provide me clues in resolving
this problem.
My files looks like as below
Header file:
#includeiostream
#includequeue
using namespace std;
typedef unsigned long pointer;
struct BTXNode
{
int data;
struct BTXNode* fleft;
struct BTXNode* fright;
};
class BTX
{
struct BTXNode *root;
public:
BTX()
{
root=NULL;
}
struct BTXNode* getNode(int data);
int insertAtLeaf(struct BTXNode* node);
};
--
CPP file
---
#include btf_xor.h
struct BTXNode* BTX::getNode(int data)
{
struct BTXNode* node=new BTXNode();
node-data=data;
node-fleft=NULL;
node-fright=NULL;
return node;
}
int BTX::insertAtLeaf(struct BTXNode* nd)
{
coutinsertAtLeaf Data is nd-dataendl;
bool set_ind=true;
bool right_ind=false;
struct BTXNode *parent=NULL;
if(!root)
{
root=nd;
return 1;
}
queueBTXNode* q;
q.push(root);
q.push(NULL);
while(!q.empty() set_ind)
{
struct BTXNode *temp=q.front();
q.pop();
if(temp)
{
couttemp-data istemp-dataendl;
if(temp-fleft != parent)
{
struct BTXNode* left=(struct BTXNode*)
((pointer)temp-
fleft^(pointer)parent);
q.push(left);
right_ind=true;
}
else
{
nd-fleft=(struct BTXNode*)
((pointer)temp ^ (pointer)nd-fleft);
nd-fright=(struct BTXNode*)
((pointer)temp ^ (pointer)nd-fright);
//temp-fleft=(struct BTXNode*)
((pointer)nd ^ (pointer)parent);
temp-fleft=(struct BTXNode*)
((pointer)nd ^ (pointer)temp-fleft);
right_ind=false;
set_ind=false;
}
if(right_ind)
{
if(temp-fright != parent)
{
struct BTXNode* right=(struct
BTXNode*)((pointer)temp-
fright^(pointer)parent);
q.push(right);
right_ind=true;
}
else
{
nd-fright=(struct BTXNode*)
((pointer)temp ^
(pointer)nd-fright);
nd-fleft=(struct BTXNode*)
((pointer)temp ^ (pointer)nd-
fleft);
//temp-fright=(struct BTXNode*)
((pointer)nd ^
(pointer)parent);
temp-fright=(struct BTXNode*)
((pointer)nd ^ (pointer)temp-
fright);
set_ind=false;
}
}
parent=temp;
}
else
{
if(!q.empty())
{
q.push(NULL);
}
}
}
}
int main()
{
BTX btx;
btx.insertAtLeaf(btx.getNode(10) );
btx.insertAtLeaf(btx.getNode(8));
btx.insertAtLeaf(btx.getNode(12));
btx.insertAtLeaf(btx.getNode(7));
btx.insertAtLeaf(btx.getNode(9));
btx.insertAtLeaf(btx.getNode(11));
btx.insertAtLeaf(btx.getNode(13));
return 0;
}
Regards
Sunil
--
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] If anyone have these books please mail
1.Mastering Java 2 2. Java 2 by Ivor Horton -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] [brain teaser] Trick Teaser Puzzle 20april
* Trick Teaser Puzzle Rhonda will go see ballet but not opera. Her favorite number is eight and she doesn't like nine. She likes salmon but not trout. She hates Mondays but likes Wednesdays. Does she use a comb or a brush? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/trick-teaser-puzzle-20april.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] If anyone have this book please mail me Thanks in advance
Could you please mail me the URL/PDF of this. the above link seems not working for me *Subhransu Panigrahi * *Mobile:* *+91-9840931538* *Email:* subhransu.panigr...@gmail.com On Wed, Apr 20, 2011 at 7:22 AM, D.N.Vishwakarma@IITR deok...@gmail.comwrote: *I've already got But thanks for your link * On Wed, Apr 20, 2011 at 5:32 AM, DIPANKAR DUTTA dutta.dipanka...@gmail.com wrote: plz chk the folowing link.. www.*mediafire*.com/?692caj1v154c5kc On Tue, Apr 19, 2011 at 11:05 PM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: Cracking the Coding Interview by *Gayle Laakmannhttp://pothi.com/pothi/search/google?cx=014194668748364006794:ovhp_xhwczgcof=FORID:11query=Gayle%20Laakmannop=Searchform_id=google_cse_searchbox_form * -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, -- DIPANKAR DUTTA Visiting Research Scholar Dept of Computing, Macquarie University, Sydney, Australia ph.no-+61 416381145 email: dipankar.du...@mq.edu.au --- M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- 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 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser] Trick Teaser Puzzle 20april
comb. all the words she like are using silent alphabets. :D On Wed, Apr 20, 2011 at 1:25 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * Trick Teaser Puzzle Rhonda will go see ballet but not opera. Her favorite number is eight and she doesn't like nine. She likes salmon but not trout. She hates Mondays but likes Wednesdays. Does she use a comb or a brush? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/trick-teaser-puzzle-20april.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshit Gangal Fourth Year Undergraduate Student Dept. of Computer Science JIIT, Noida , India -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser ] Identical Twin Puzzle 19april
date of birth are same but birth's time is different On Tue, Apr 19, 2011 at 1:30 AM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * Identical Twin Puzzle Two women apply for a job. They are identical. They have the same mother, father and birthday. The interviewer asks, 'Are you twins?' to which they honestly reply, 'No'. How is this possible? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/identical-twin-puzzle-19april.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser ] Identical Twin Puzzle 19april
On Wed, Apr 20, 2011 at 8:09 PM, arjoo kumar 2009ar...@gmail.com wrote: *date of birth are same but birth's time is different* STILL they remains twin.. they were triplets On Tue, Apr 19, 2011 at 1:30 AM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * Identical Twin Puzzle Two women apply for a job. They are identical. They have the same mother, father and birthday. The interviewer asks, 'Are you twins?' to which they honestly reply, 'No'. How is this possible? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/identical-twin-puzzle-19april.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshit Gangal Fourth Year Undergraduate Student Dept. of Computer Science JIIT, Noida , India -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
RE: [algogeeks] [brain teaser ] Identical Twin Puzzle 19april
Ru probably they ve a surrogate mother... :/ -Original message- From: Harshit Gangal Sent: 20/04/2011, 8:56 pm To: algogeeks@googlegroups.com Subject: Re: [algogeeks] [brain teaser ] Identical Twin Puzzle 19april On Wed, Apr 20, 2011 at 8:09 PM, arjoo kumar 2009ar...@gmail.com wrote: *date of birth are same but birth's time is different* STILL they remains twin.. they were triplets On Tue, Apr 19, 2011 at 1:30 AM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * Identical Twin Puzzle Two women apply for a job. They are identical. They have the same mother, father and birthday. The interviewer asks, 'Are you twins?' to which they honestly reply, 'No'. How is this possible? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/identical-twin-puzzle-19april.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshit Gangal Fourth Year Undergraduate Student Dept. of Computer Science JIIT, Noida , India -- 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 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Square of Large integer
Algo can be derived from these equations: (x + 1) * y = (x * y) + y (2*x) * y = 2 * (x * y). Runs in O(log number). -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Probabilistic Analysis and Randomized Algorithms
Hey, I spend most of my time researching systems computing, but these problems are fun and interesting (so bare with me :) This problem is from Chapter 5 of Introduction to Algorithms (MIT Press) 5.1-2 Describe an implementation of the procedure RANDOM(a,b) that only makes calls to RANDOM(0,1). What is the expected running time of your procedure, as a function of a and b? Here is my approach... It's asking for the expected running time of the procedure, and the expected value is E[X] = sum (0 to n) x*p(x) In this case n = b-a+1 p(x) = RANDOM(0,1) = 1/2 E[X] = (1/2) * sum (0 to (b-a+1)) 1 = (b-a+1)/2 It seems that the correct answer, I've found on the internet is lg(b-a) +1 I can sort of see this, because the first time we call random will be (1/2), second (1/2)*(1/2), etc.. which would be n calls.. (1/2^n). Can anyone explain further why my answer is probably wrong, and the lg(b-a)+1 is correct? Any help is greatly appreciated, Thank You! -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Reading Huge input from the terminal in least time.
You could just use a pseudo-random number generator to fill in the array. You may also want to consider the data type (each unsigned int would be 4 bytes, where a unsigned char would be 1 byte). Or, If it's truly necessary to read this much data from the console... You could use unix pipes, (cat file.out | ./myprog) pipes in unix shells will redirect from the standard i/o... The format of the file.out should be input0 input1 input2 ... inputn where I guess in your case n = 10^6 That should work, but I don't code in c++ (only c) On Apr 19, 10:11 pm, shubham shubh2...@gmail.com wrote: Hello Geeks, Suppose we have a 2-d array arr[1000][1000] capable of storing 10^6 elements in it. Input is supplied one row at a time. Then what is the best possible way to read this much data in the least amount of time as scanf() or cin takes a lot of time? -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Company in Canada
*Company in Canada You can Register your business in Canada You don’t need to go there. Ask us! http://bit.ly/biZzwiz http://bit.ly/biZzwiz* -- If you would like to get daily pictures We've started a Google Group to allow our visitors to get daily funny and Crazy Pictures , You can join this group for free , go to... *http://groups.google.com/group/WomenForum/subscribe* -- 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 more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
