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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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
2
i hope you get my point.
Siddhant Khanna
On Feb 9, 7:38 pm, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}
--
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: 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. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -
--
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: 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 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 sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -
--
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: Binary Search Tree Question
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 sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -
--
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: 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 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:
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. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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: 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 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 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:
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. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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] 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 of traversal , we are done with
function((*node)-Left); now next recursion for root node is
function((*node)-Right);.
function((*node)-Right); --- this will again do reversing steps in
root-right subtree.(reverting back the old state).
after backtracking it reaches root.
but wait there is no swapping part after function((*node)-Right) , but it
is after function((*node)-Left);
but we have as discussed before function((*node)-Right) is the only
recursion root needs to complete in order move out of the function.
hence root-left and root-right remain swapped.
but program is similar to swapping root-left and root-right which can be
done in constant time but taken O(n) to do the same.
hope you have understood it :)
On Fri, Feb 10, 2012 at 10:16 AM, Rahul Menon menonrahul1...@gmail.comwrote:
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 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:
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. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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] 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 ankitsamb...@gmail.comwrote:
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=NULL; //Make it NULL so that we do not traverse it
again
temp=temp-left;
}
//Now top of the stack contains the minimum node.
//Now we will do inorder traversal
while(top!=-1)
{
temp=stack[top];
count++; //Increment the count for every eleemnt
traversed
if(count==k) //If count reaches k, we have kth smallest
element as the top of the stack
return stack[top]-value;
else if(temp-left!=NULL)
{
stack[++top]=temp-left;
temp-left=NULL; //Make it NULL so that we do not traverse
it again
count++;
}
else if(temp-right!=NULL)
{
stack[++top]=temp-right;
temp-right=NULL; //Make it NULL so that we do not
traverse it again
count++;
}
else
top--;
}
}
--
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.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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] Re: binary search tree question!!!!
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 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=NULL; //Make it NULL so that we do not traverse it
again
temp=temp-left;
}
//Now top of the stack contains the minimum node.
//Now we will do inorder traversal
while(top!=-1)
{
temp=stack[top];
count++; //Increment the count for every eleemnt
traversed
if(count==k) //If count reaches k, we have kth smallest
element as the top of the stack
return stack[top]-value;
else if(temp-left!=NULL)
{
stack[++top]=temp-left;
temp-left=NULL; //Make it NULL so that we do not
traverse it again
count++;
}
else if(temp-right!=NULL)
{
stack[++top]=temp-right;
temp-right=NULL; //Make it NULL so that we do not
traverse it again
count++;
}
else
top--;
}
}
--
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.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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.
--
Tushar Bindal
Computer Engineering
Delhi College of Engineering
Mob: +919818442705
E-Mail : tushicom...@gmail.com
Website: www.jugadengg.com
--
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: binary search tree question!!!!
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 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 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 any static/global variable. You can’t pass the
value k
to any function also
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue
that counts!
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] 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 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 = 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 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 any static/global variable. You can’t pass the
value k
to any function also
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue
that counts!
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] 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(no more nodes to traverse)
, add the condition that ( k != 0)
^^ This will keep a check on value of k after each loop run.
Hope I am clear in explaining.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/aHwinvhUrs4J.
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] 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=NULL; //Make it NULL so that we do not traverse it
again
temp=temp-left;
}
//Now top of the stack contains the minimum node.
//Now we will do inorder traversal
while(top!=-1)
{
temp=stack[top];
count++; //Increment the count for every eleemnt traversed
if(count==k) //If count reaches k, we have kth smallest
element as the top of the stack
return stack[top]-value;
else if(temp-left!=NULL)
{
stack[++top]=temp-left;
temp-left=NULL; //Make it NULL so that we do not traverse
it again
count++;
}
else if(temp-right!=NULL)
{
stack[++top]=temp-right;
temp-right=NULL; //Make it NULL so that we do not traverse
it again
count++;
}
else
top--;
}
}
--
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: 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 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 any static/global variable. You can’t pass the value k to any function also -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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] 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 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 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 any static/global variable. You can’t pass the
value k
to any function also
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue
that counts!
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
