Re: [algogeeks] Re: BST in file
@asit dhal,
in order of any BST is increasing order.
so required is only either preorder/postorder
surender
On Tue, Sep 27, 2011 at 12:42 AM, Gene gene.ress...@gmail.com wrote:
Here is a little program to show how it works. It's a nice little
problem. There is also a coding with recursion.
#include stdio.h
#include stdlib.h
typedef struct node_s {
int data;
struct node_s *left, *right;
} NODE;
void print_tree(NODE *tree)
{
if (tree == NULL) return;
print_tree(tree-left);
printf( %d, tree-data);
print_tree(tree-right);
}
void save_tree(NODE *tree)
{
if (tree == NULL) return;
printf(%d\n, tree-data);
save_tree(tree-left);
save_tree(tree-right);
}
NODE *new_node(int data)
{
NODE *node = malloc(sizeof *node);
node-data = data;
node-left = node-right = NULL;
return node;
}
NODE *read_tree(void)
{
int data, sp = 0;
NODE *root, *node, *last, *stack[1];
// Loop invariants: Root holds tree root.
// Last holds last node added.
// Stack[i] holds the unique node at
// level i to which a right child might
// still be added.
root = last = NULL;
while (scanf(%d, data) == 1) {
node = new_node(data);
if (root == NULL)
root = node;
else {
// If new node has key last, it must
// be the left child of last. Attach and
// push onto stack because we still
// may receive a right child.
if (data last-data) {
last-left = node;
stack[sp++] = last;
}
// Else it has key last, so if the key is also
// the deepest level waiting for a right child, it
// can only be right child of the last node.
else if (sp == 0 || data stack[sp - 1]-data)
last-right = node;
// Else it must be the right child of an ancestor.
// The possible ancestors are on the stack.
// Pop the stack until we find the last ancestor
// with larger key and attach there.
else {
while (sp 1 data stack[sp - 2]-data)
--sp;
stack[--sp]-right = node;
}
}
last = node;
}
return root;
}
int main(void)
{
print_tree(read_tree());
return 0;
}
On Sep 24, 8:28 pm, vikas vikas.rastogi2...@gmail.com wrote:
if this is simple BST then only preorder will suffice
On Sep 24, 10:16 pm, wetheart gumnaamsm...@yahoo.com wrote:
You can put the array representation of binary tree directly, with
some obvious modifications ofcourse :)
On Sep 24, 5:38 pm, asdqwe ayushgoel...@gmail.com wrote:
you can put two traversals of three (inorder, preorder or postorder)
in the file..
Two traversals are enough to dedicate a particular tree.
On Sep 24, 4:05 pm, Asit Dhal lipu...@gmail.com wrote:
I need to print a binary search tree in file. When I will retrieve
the same
tree from the file.
I have thought about printing in xml format like this
100
/ \
50 150
/ \ / \
30 70 120 200
Level 0
100
Level 1
50
Level 2
30
/Level2
Level 2
70
/Level 2
/Level 1
Level 1
150
Level 2
120
/Level 2
Level 2
200
/level 2
/level 1
/level 0
I don't know will this be the best solution or not.
Please suggest me how to approach it or some better solution.
Regards
Asithttp://kodeyard.blogspot.com/- 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.
[algogeeks] Re: BST to DLL spirally
just use the two stacks here and do the level order traversal in spiral order and keep down prev pointer each time and just maintain the doubly linked i think it is pretty gud hint :) -- 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/-/iHbjfHkgHl4J. 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: BST to DLL spirally
use one Queue instead of stacks. this was one of amazon written question for me Sini On Tue, Sep 27, 2011 at 10:09 PM, geeks ankurshukla.h...@gmail.com wrote: just use the two stacks here and do the level order traversal in spiral order and keep down prev pointer each time and just maintain the doubly linked i think it is pretty gud hint :) -- 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/-/iHbjfHkgHl4J. 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: BST to DLL spirally
using two stacks or using a queue and a stack ... these are obvious solutions .. Just want to know if there exists an iterative way without extra space !!! I should've mentioned these details earlier .. sorry for that !! ~raju On Tue, Sep 27, 2011 at 10:09 PM, geeks ankurshukla.h...@gmail.com wrote: just use the two stacks here and do the level order traversal in spiral order and keep down prev pointer each time and just maintain the doubly linked i think it is pretty gud hint :) -- 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/-/iHbjfHkgHl4J. 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: BST in file
Here is a little program to show how it works. It's a nice little
problem. There is also a coding with recursion.
#include stdio.h
#include stdlib.h
typedef struct node_s {
int data;
struct node_s *left, *right;
} NODE;
void print_tree(NODE *tree)
{
if (tree == NULL) return;
print_tree(tree-left);
printf( %d, tree-data);
print_tree(tree-right);
}
void save_tree(NODE *tree)
{
if (tree == NULL) return;
printf(%d\n, tree-data);
save_tree(tree-left);
save_tree(tree-right);
}
NODE *new_node(int data)
{
NODE *node = malloc(sizeof *node);
node-data = data;
node-left = node-right = NULL;
return node;
}
NODE *read_tree(void)
{
int data, sp = 0;
NODE *root, *node, *last, *stack[1];
// Loop invariants: Root holds tree root.
// Last holds last node added.
// Stack[i] holds the unique node at
// level i to which a right child might
// still be added.
root = last = NULL;
while (scanf(%d, data) == 1) {
node = new_node(data);
if (root == NULL)
root = node;
else {
// If new node has key last, it must
// be the left child of last. Attach and
// push onto stack because we still
// may receive a right child.
if (data last-data) {
last-left = node;
stack[sp++] = last;
}
// Else it has key last, so if the key is also
// the deepest level waiting for a right child, it
// can only be right child of the last node.
else if (sp == 0 || data stack[sp - 1]-data)
last-right = node;
// Else it must be the right child of an ancestor.
// The possible ancestors are on the stack.
// Pop the stack until we find the last ancestor
// with larger key and attach there.
else {
while (sp 1 data stack[sp - 2]-data)
--sp;
stack[--sp]-right = node;
}
}
last = node;
}
return root;
}
int main(void)
{
print_tree(read_tree());
return 0;
}
On Sep 24, 8:28 pm, vikas vikas.rastogi2...@gmail.com wrote:
if this is simple BST then only preorder will suffice
On Sep 24, 10:16 pm, wetheart gumnaamsm...@yahoo.com wrote:
You can put the array representation of binary tree directly, with
some obvious modifications ofcourse :)
On Sep 24, 5:38 pm, asdqwe ayushgoel...@gmail.com wrote:
you can put two traversals of three (inorder, preorder or postorder)
in the file..
Two traversals are enough to dedicate a particular tree.
On Sep 24, 4:05 pm, Asit Dhal lipu...@gmail.com wrote:
I need to print a binary search tree in file. When I will retrieve the
same
tree from the file.
I have thought about printing in xml format like this
100
/ \
50 150
/ \ / \
30 70 120 200
Level 0
100
Level 1
50
Level 2
30
/Level2
Level 2
70
/Level 2
/Level 1
Level 1
150
Level 2
120
/Level 2
Level 2
200
/level 2
/level 1
/level 0
I don't know will this be the best solution or not.
Please suggest me how to approach it or some better solution.
Regards
Asithttp://kodeyard.blogspot.com/- 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: BST in file
What does it mean by simple BST ?? -- 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/-/Q5mtepDUIx0J. 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: BST in file
you can put two traversals of three (inorder, preorder or postorder) in the file.. Two traversals are enough to dedicate a particular tree. On Sep 24, 4:05 pm, Asit Dhal lipu...@gmail.com wrote: I need to print a binary search tree in file. When I will retrieve the same tree from the file. I have thought about printing in xml format like this 100 / \ 50 150 / \ / \ 30 70 120 200 Level 0 100 Level 1 50 Level 2 30 /Level2 Level 2 70 /Level 2 /Level 1 Level 1 150 Level 2 120 /Level 2 Level 2 200 /level 2 /level 1 /level 0 I don't know will this be the best solution or not. Please suggest me how to approach it or some better solution. Regards Asithttp://kodeyard.blogspot.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: BST in file
You can put the array representation of binary tree directly, with some obvious modifications ofcourse :) On Sep 24, 5:38 pm, asdqwe ayushgoel...@gmail.com wrote: you can put two traversals of three (inorder, preorder or postorder) in the file.. Two traversals are enough to dedicate a particular tree. On Sep 24, 4:05 pm, Asit Dhal lipu...@gmail.com wrote: I need to print a binary search tree in file. When I will retrieve the same tree from the file. I have thought about printing in xml format like this 100 / \ 50 150 / \ / \ 30 70 120 200 Level 0 100 Level 1 50 Level 2 30 /Level2 Level 2 70 /Level 2 /Level 1 Level 1 150 Level 2 120 /Level 2 Level 2 200 /level 2 /level 1 /level 0 I don't know will this be the best solution or not. Please suggest me how to approach it or some better solution. Regards Asithttp://kodeyard.blogspot.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: BST in file
if this is simple BST then only preorder will suffice On Sep 24, 10:16 pm, wetheart gumnaamsm...@yahoo.com wrote: You can put the array representation of binary tree directly, with some obvious modifications ofcourse :) On Sep 24, 5:38 pm, asdqwe ayushgoel...@gmail.com wrote: you can put two traversals of three (inorder, preorder or postorder) in the file.. Two traversals are enough to dedicate a particular tree. On Sep 24, 4:05 pm, Asit Dhal lipu...@gmail.com wrote: I need to print a binary search tree in file. When I will retrieve the same tree from the file. I have thought about printing in xml format like this 100 / \ 50 150 / \ / \ 30 70 120 200 Level 0 100 Level 1 50 Level 2 30 /Level2 Level 2 70 /Level 2 /Level 1 Level 1 150 Level 2 120 /Level 2 Level 2 200 /level 2 /level 1 /level 0 I don't know will this be the best solution or not. Please suggest me how to approach it or some better solution. Regards Asithttp://kodeyard.blogspot.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: BST
If nothing is allowed , as in extra space etcetera We can use morris traversal to find the inorder of the tree . On Jun 19, 3:25 am, kumar vr kumarg...@gmail.com wrote: Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.comwrote: then you can use iterative method instead of recursion ... -- 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: BST
@sankalp: ya, that solved the problem :) On Sun, Jun 19, 2011 at 6:50 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: If nothing is allowed , as in extra space etcetera We can use morris traversal to find the inorder of the tree . On Jun 19, 3:25 am, kumar vr kumarg...@gmail.com wrote: Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.com wrote: then you can use iterative method instead of recursion ... -- 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. -- 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: BST
http://anandtechblog.blogspot.com/2011/05/find-median-in-bst.html On Sun, Jun 19, 2011 at 6:32 AM, Akshata Sharma akshatasharm...@gmail.comwrote: @sankalp: ya, that solved the problem :) On Sun, Jun 19, 2011 at 6:50 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: If nothing is allowed , as in extra space etcetera We can use morris traversal to find the inorder of the tree . On Jun 19, 3:25 am, kumar vr kumarg...@gmail.com wrote: Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.com wrote: then you can use iterative method instead of recursion ... -- 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. -- 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: BST
@sankalp would you please elaborate morris traversal . On Sun, Jun 19, 2011 at 9:41 PM, Anand anandut2...@gmail.com wrote: http://anandtechblog.blogspot.com/2011/05/find-median-in-bst.html On Sun, Jun 19, 2011 at 6:32 AM, Akshata Sharma akshatasharm...@gmail.com wrote: @sankalp: ya, that solved the problem :) On Sun, Jun 19, 2011 at 6:50 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: If nothing is allowed , as in extra space etcetera We can use morris traversal to find the inorder of the tree . On Jun 19, 3:25 am, kumar vr kumarg...@gmail.com wrote: Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.com wrote: then you can use iterative method instead of recursion ... -- 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. -- 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. -- 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: BST
You can find Morris Traversal in blog below http://anandtechblog.blogspot.com/2011/05/find-median-in-bst.html On Sun, Jun 19, 2011 at 11:31 AM, abc abc may.i.answ...@gmail.com wrote: @sankalp would you please elaborate morris traversal . On Sun, Jun 19, 2011 at 9:41 PM, Anand anandut2...@gmail.com wrote: http://anandtechblog.blogspot.com/2011/05/find-median-in-bst.html On Sun, Jun 19, 2011 at 6:32 AM, Akshata Sharma akshatasharm...@gmail.com wrote: @sankalp: ya, that solved the problem :) On Sun, Jun 19, 2011 at 6:50 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: If nothing is allowed , as in extra space etcetera We can use morris traversal to find the inorder of the tree . On Jun 19, 3:25 am, kumar vr kumarg...@gmail.com wrote: Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.com wrote: then you can use iterative method instead of recursion ... -- 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. -- 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. -- 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: BST
If you are allowed an extra integer per node, then you can maintain in each node a count of the number of nodes in the subtree rooted at that node. This can be maintained at no additional asymptotic cost in the insert, delete, and balance operations (if you're balancing). With these counts in each node, it is easy to find the median at any time in O(log n) time. In fact you can find the k'th element for any k. Conversely, you can find any element using its search key (in O(log n) time) and at no extra cost get, k, which in this case is called the key's order statistic. -- 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/-/H9Fq-cazLdkJ. 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: BST+Heap
1. Insert the node(order of insertion is irrelevant) in any order according to the binary search tree properties. 2. Compare the j value of node with its parent recursively (bottom up) and then perform rotations to restore the Heap property. On Thu, Jun 9, 2011 at 12:38 AM, mukesh tiwari mukeshtiwari.ii...@gmail.com wrote: What you explained is the property of Treap data structure . You can have a look at wiki [ http://en.wikipedia.org/wiki/Treap ] or you can search google for treap. On Jun 8, 8:15 pm, Akshata Sharma akshatasharm...@gmail.com wrote: A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key. You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree -- 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: BST+Heap
What you explained is the property of Treap data structure . You can have a look at wiki [ http://en.wikipedia.org/wiki/Treap ] or you can search google for treap. On Jun 8, 8:15 pm, Akshata Sharma akshatasharm...@gmail.com wrote: A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key. You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree -- 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: BST insertion
you should return results from the recursive functions, e.g: if(num (*bt)-data) result = insert_node(((*bt)-left),num); ... return result; -- 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: BST Question
The suggestion will work if the root is known to have entry equal to zero. (Even it is less than 0, there is a chance that a negative an reside in right sub-tree whose value is 0 but greater than the negative value of the root). If the entry of the root is zero then we can do the inorder traversal. Also if the BST is rooted tree (say there is a special mark for identifying the root) then we can identify the root and use this to terminate the algorithm after printing the result. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST in BT
Maximum Sized Binary Search Tree in a Binary Tree: http://www.rawkam.com/?p=822 On Mon, Sep 27, 2010 at 10:34 AM, Chonku cho...@gmail.com wrote: @Prodigy As per your example, 8 15 20 25 which is the is indeed the maximum binary search tree in this binary tree is only a solution to smaller problem used to solve a bigger problem. The solution to smaller problem can be translated directly to the solution of the bigger problem. On Mon, Sep 27, 2010 at 8:28 AM, prodigy 1abhishekshu...@gmail.comwrote: 15 /\ 8 25 /\ 20 22 On Sep 26, 10:45 am, Chonku cho...@gmail.com wrote: This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. Your idea will fail for above case. In Order = 8 15 20 25 22 longest continuous sequence of numbers in ascending order = 8 15 20 25 But that's not the answer (I hope you realize what correct output would be ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST in BT
For solution to this problem see
http://groups.google.co.in/group/algogeeks/browse_thread/thread/adc95dcf96020a7/2943fd3c5a116fee?hl=enlnk=gstq=binary+tree+to+binary+serach+tree#
In that thread, I have a doubt regarding solution posted by @Algoose
Chase. The code posted is good as I feel except for the condition
if( NodeL-Data root-data)
{
}
if( NodeR-Data = root-data)
{
}
Here If you find that the present node's (say 'n1') value if less than
the MAX (say 'n2' ) of so far constructed BST in the left tree, then
if is for sure that that MAX ('n2') of the left tree will replace the
present node 'n1'. This will make sure that all nodes to the left are
less than the new root 'n2', but we are not sure that the remaining
nodes n the left tree are all less than 'n1'.
So in if( NodeL-Data root-data) condition, temp = root-data;
root-data = NodeL-data is correct but instead of doing
Nodel-data = root-data;
BinarytoBST(NodeL)
we should simply say
deleteNode(tree-left,NodeL);//This will delete NodeL from a BST
rooted at tree-left, taking into account delete conditions for
deleting right most child of BST //(because NodeL was the
right most child)
InsertNode(tree-left,temp);
Do share your views.
Thanks,
Sourav
On Sep 27, 7:58 am, prodigy 1abhishekshu...@gmail.com wrote:
15
/ \
8 25
/ \
20 22
On Sep 26, 10:45 am, Chonku cho...@gmail.com wrote:
This can also be done if we do an inorder traversal of the binary tree and
look for the longest continuous sequence of numbers in ascending order.
Your idea will fail for above case.
In Order = 8 15 20 25 22
longest continuous sequence of numbers in ascending order = 8 15 20
25
But that's not the answer (I hope you realize what correct output
would be )
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST in BT
@Prodigy As per your example, 8 15 20 25 which is the is indeed the maximum binary search tree in this binary tree is only a solution to smaller problem used to solve a bigger problem. The solution to smaller problem can be translated directly to the solution of the bigger problem. On Mon, Sep 27, 2010 at 8:28 AM, prodigy 1abhishekshu...@gmail.com wrote: 15 /\ 8 25 /\ 20 22 On Sep 26, 10:45 am, Chonku cho...@gmail.com wrote: This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. Your idea will fail for above case. In Order = 8 15 20 25 22 longest continuous sequence of numbers in ascending order = 8 15 20 25 But that's not the answer (I hope you realize what correct output would be ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST in BT
BSTP : Root's right and left subtrees are BST and value at Root is (greater than largest of left) and (smaller than lowest of right). if BSTP is true, size of this BST is sum of (size of left subtree) and (size of right subtree) plus 1. Compare this value with global maximum. Do it recursively. See the code here http://pastebin.com/xwXXTEnP -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST in BT
This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. On Sun, Sep 26, 2010 at 11:10 AM, mac adobe macatad...@gmail.com wrote: No parody .. that would be another doubt :( On Sat, Sep 25, 2010 at 11:03 PM, prodigy 1abhishekshu...@gmail.comwrote: By maintaining a current maximum and a global maximum. You do know how to verify a BT is BST . http://pastebin.com/xwXXTEnP On Sep 25, 9:04 pm, mac adobe macatad...@gmail.com wrote: How would you identify a binary search tree of maximum nodes in a binary tree ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST in BT
15 /\ 8 25 /\ 20 22 On Sep 26, 10:45 am, Chonku cho...@gmail.com wrote: This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. Your idea will fail for above case. In Order = 8 15 20 25 22 longest continuous sequence of numbers in ascending order = 8 15 20 25 But that's not the answer (I hope you realize what correct output would be ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST in BT
No parody .. that would be another doubt :( On Sat, Sep 25, 2010 at 11:03 PM, prodigy 1abhishekshu...@gmail.com wrote: By maintaining a current maximum and a global maximum. You do know how to verify a BT is BST . http://pastebin.com/xwXXTEnP On Sep 25, 9:04 pm, mac adobe macatad...@gmail.com wrote: How would you identify a binary search tree of maximum nodes in a binary tree ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST in BT
@parody :..and how would that find me a maximum size BST .. ?? ( for checking if this BT is BST i would do inorder traversal and see if it is increasing ) On Sun, Sep 26, 2010 at 11:10 AM, mac adobe macatad...@gmail.com wrote: No parody .. that would be another doubt :( On Sat, Sep 25, 2010 at 11:03 PM, prodigy 1abhishekshu...@gmail.comwrote: By maintaining a current maximum and a global maximum. You do know how to verify a BT is BST . http://pastebin.com/xwXXTEnP On Sep 25, 9:04 pm, mac adobe macatad...@gmail.com wrote: How would you identify a binary search tree of maximum nodes in a binary tree ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST Problem
@arvind: had i knwn would hv posted it On Aug 23, 8:59 am, R.ARAVINDH aravindhr...@gmail.com wrote: @giri: can u post d correct answer?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
Perform inorder traversal and store in an array.
low = 0, high = size-1
while(low=high)
{
if ( a[low] + a[high] sum)
low++;
else if (a[low] + a[high] sum)
high--;
else
return a[high] and [low]
}
On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH aravindhr...@gmail.com wrote:
@giri:
can u post d correct answer??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST Problem
I am not sure if I am repeating the answer: The problem will reduce to find the pair of elements which will sum up to a particular number. Then read the below article, http://www.rawkam.com/?p=345 On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH aravindhr...@gmail.com wrote: @giri: can u post d correct answer?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST Problem
can v do like this???
findnodes(root,sum)
{
if(root==abs(sum-root-data))
print (the data is root-data, sum-(root-data));
else
if(rootabs(sum-root-data))
findnodes(root-right,sum-root-data)
else if(rootabs(sum-root-data))
findnodes(root-left,sum-root-data)
else if(root-left==NULL || root-right==NULL) print(root,sum-root);
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST Problem
for the above post i have assumed that the two nodes whose sum is k is present in the BST... so correct me if m wrong -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
frnd check ur code.. t contains much errors..
consider the following eg.:
k=5;3
1 4
2 5
On Aug 22, 2:30 pm, R.ARAVINDH aravindhr...@gmail.com wrote:
can v do like this???
findnodes(root,sum)
{
if(root==abs(sum-root-data))
print (the data is root-data, sum-(root-data));
else
if(rootabs(sum-root-data))
findnodes(root-right,sum-root-data)
else if(rootabs(sum-root-data))
findnodes(root-left,sum-root-data)
else if(root-left==NULL || root-right==NULL) print(root,sum-root);
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST Problem
@giri: thnx frnd...sorry ppl . ignore my post :( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
@giri: can u post d correct answer?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
@Sekin. Sort the elements (increasing order). This has already been mentioned. So, answer will be 1, 100. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
Avik, yes the answer is obvious but your code doesn't find that. that 2 pointer approach is the correct one. On Tue, Aug 10, 2010 at 12:07 AM, Avik Mitra tutai...@gmail.com wrote: @Sekin. Sort the elements (increasing order). This has already been mentioned. So, answer will be 1, 100. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST Problem
@Sekin Yes that's true.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST sort
Do you mean to convert a BST to a HEAP? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
as a hint, convert the BST to a sorted array and take two pointers one
pointing to the first number and the other pointing to the last. Then, move
pointers appropriately to find the two numbers summing up to k.
complexity: O(n)
2010/8/5 Seçkin Can Şahin seckincansa...@gmail.com
what about the case:
array : 1 3 10 100 and k = 101. Your code doesn't find it I suppose.
On Thu, Aug 5, 2010 at 11:15 PM, Avik Mitra tutai...@gmail.com wrote:
Inorder traversal of the BST will give elements in sorted way. Let us
assume that the sorted elements are in an array A of length N.
set i=1;
while i N-1
{
if a[i] k, then output: No such node
else if(a[i]==k)
{
if (a[i+1] ==0)
output: Two nodes found BREAK;
else
output: No such node. BREAK.
}
else if(a[i] k )
{
if(a[i]+a[i+1]==k)
output: Two nodes found BREAK.
else if(a[i]+a[i+1] k)
output: No such node BREAK
else if(a[i] +a[i+1] k)
i++ ;
}
}//End of while-loop.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST Problem
the solution elegant..but is there any on the fly method by just exploiting the BST propertyby using left and right pointers -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST Problem
Two inorders would achieve the same thing without using an array. One pointer running inorder with LDR and other pointer running inorder with RDL. Compare the sum at the two nodes and then adjust them accordingly. On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar manjunath.n...@gmail.comwrote: the solution elegant..but is there any on the fly method by just exploiting the BST propertyby using left and right pointers -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST Problem
do the inorder traversal of the bst ...this gives the sorted array..
from that use
int i=0,j=length(array)
while(ij)
{
if(array[i]+array[j]sum)
--j;
else if(array[i]+array[j]sum)
++i;
else if((array[i]+array[j])==sum)
return i,j
else
++i,--j;
}
On Fri, Aug 6, 2010 at 3:10 PM, Chonku cho...@gmail.com wrote:
Two inorders would achieve the same thing without using an array. One
pointer running inorder with LDR and other pointer running inorder with RDL.
Compare the sum at the two nodes and then adjust them accordingly.
On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar
manjunath.n...@gmail.com wrote:
the solution elegant..but is there any on the fly method by just
exploiting the BST propertyby using left and right pointers
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST Problem
Chonku, you can do that only when you have the links to parent nodes. I
couldn't come up with a way of doing what you said on a basic BST(nodes
having pointers only to their 2 children) that is why I suggested using an
array. It doesn't change the overall complexity but if you have an idea
about how implement your idea on a basic BST, I would like to hear it.
Thanks,
Seckin
On Fri, Aug 6, 2010 at 2:56 AM, sharad kumar aryansmit3...@gmail.comwrote:
do the inorder traversal of the bst ...this gives the sorted array..
from that use
int i=0,j=length(array)
while(ij)
{
if(array[i]+array[j]sum)
--j;
else if(array[i]+array[j]sum)
++i;
else if((array[i]+array[j])==sum)
return i,j
else
++i,--j;
}
On Fri, Aug 6, 2010 at 3:10 PM, Chonku cho...@gmail.com wrote:
Two inorders would achieve the same thing without using an array. One
pointer running inorder with LDR and other pointer running inorder with RDL.
Compare the sum at the two nodes and then adjust them accordingly.
On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar
manjunath.n...@gmail.com wrote:
the solution elegant..but is there any on the fly method by just
exploiting the BST propertyby using left and right pointers
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: BST
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem in
O(n) time with less than O(n) memory.
On Jul 26, 6:18 am, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal
to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal
to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
Hey could you please give a very brief on what is meant by threads in
bst?
On Jul 27, 5:17 am, Gene gene.ress...@gmail.com wrote:
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is
equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
Look up threaded tree in wikipedia.
On Jul 26, 9:12 pm, Snoopy Me thesnoop...@gmail.com wrote:
Hey could you please give a very brief on what is meant by threads in
bst?
On Jul 27, 5:17 am, Gene gene.ress...@gmail.com wrote:
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is
equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
I think we can solve this problem by changing the right sub tree of the root
in to linked list in the following way. Here is an example
5
4 7
2 3 89
5
4 9
2 3 8
7
This gives us access to the lowest number and the highest number in the
tree. We can start with the left most child and first right child of the
root.
On 27 July 2010 07:06, Gene gene.ress...@gmail.com wrote:
Look up threaded tree in wikipedia.
On Jul 26, 9:12 pm, Snoopy Me thesnoop...@gmail.com wrote:
Hey could you please give a very brief on what is meant by threads in
bst?
On Jul 27, 5:17 am, Gene gene.ress...@gmail.com wrote:
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right?
Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The
ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem
willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com
wrote:
Given a binary search tree of n nodes, find two nodes whose sum
is equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks and Regards,
N. Ravikanth
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
@rahul how to convert bst ot doubly linked list. I m understanding the logic but not able to code give a pseudo code to understand. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST
@ above have it
node * bsttolist(node *root){
if(root==NULL) return NULL;
node *l=bsttolist(root-left);
node *r=bsttolist(root-right);
root-left=root;
root-right=root;
append(l,root);
append(l,r);
return l;
}
here append function merges two circular doubly linked lists , you can make
that on your own
On Sun, Jul 25, 2010 at 1:35 PM, Debajyoti Sarma
sarma.debajy...@gmail.comwrote:
@rahul
how to convert bst ot doubly linked list.
I m understanding the logic but not able to code
give a pseudo code to understand.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
It is simple to convert BST to sorted doubly link list
Just do inorder_traverse and add node into the linklist.
It is like following.
linklist_node *head=NULL;
mod_in_order(tree_node *root){
tree_node *temp;
temp=root;
if (root is a leaf node)
add_node_to_linklist(root); // instead of printing add
node
else {
if(root-left)
inorder(root-left);
add_node_to_linklist(root); // instead of printing add
node
if(temp-right)
inorder(root-right);
}
}
On Jul 25, 2:27 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
@ above have it
node * bsttolist(node *root){
if(root==NULL) return NULL;
node *l=bsttolist(root-left);
node *r=bsttolist(root-right);
root-left=root;
root-right=root;
append(l,root);
append(l,r);
return l;
}
here append function merges two circular doubly linked lists , you can make
that on your own
On Sun, Jul 25, 2010 at 1:35 PM, Debajyoti Sarma
sarma.debajy...@gmail.comwrote:
@rahul
how to convert bst ot doubly linked list.
I m understanding the logic but not able to code
give a pseudo code to understand.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;
}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
1 convert the BST into a sorted doubly linklist.(increasing order) It
will take O(n) time.
2 Now find two nodes in a link list whose sum is k(given no)
to find sum in linklist. take two pointers ptr1= head ptr2=tail of
linlist.
now find sum of ptr1-data + ptr2- data
while(ptr1-data ptr2- data){
if ((ptr1-data + ptr2- data )k)
ptr2= ptr2-prev;
else if ((ptr1-data + ptr2- data )k)
ptr1= ptr1-next;
else if ((ptr1-data + ptr2- data ) == k){
print_data_of_ptr1_and_ptr2;
ptr2= ptr2-prev;
ptr1= ptr1-next;
}
}
the 2nd step will take O(n) time.No added space complexity
On Jul 24, 9:29 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
@Rahil: you are correctthanks
On 24 July 2010 18:33, rahul patil rahul.deshmukhpa...@gmail.com wrote:
1 convert the BST into a sorted doubly linklist.(increasing order) It
will take O(n) time.
2 Now find two nodes in a link list whose sum is k(given no)
to find sum in linklist. take two pointers ptr1= head ptr2=tail of
linlist.
now find sum of ptr1-data + ptr2- data
while(ptr1-data ptr2- data){
if ((ptr1-data + ptr2- data )k)
ptr2= ptr2-prev;
else if ((ptr1-data + ptr2- data )k)
ptr1= ptr1-next;
else if ((ptr1-data + ptr2- data ) == k){
print_data_of_ptr1_and_ptr2;
ptr2= ptr2-prev;
ptr1= ptr1-next;
}
}
the 2nd step will take O(n) time.No added space complexity
On Jul 24, 9:29 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal
to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: BST
Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space. (ignoring recursion stack space) I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please help me out with O(n) time and O(1) space. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST
@Manish Does not a recursive solution [inorder traversal] takes an implicit stack space ? Please correct me if I am wrong ? @Rahul Can you please send us the *morris inorder pdf* link that u have shared once ? Best Regards Kaushik -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST
Sharing link for Morris Inorder http://www.scss.tcd.ie/disciplines/software_systems/fmg/fmg_web/IFMSIG/winter2000/HughGibbonsSlides.pdf Courtesy Rohit On Mon, May 17, 2010 at 3:42 PM, kaushik sur kaushik@gmail.com wrote: @Manish Does not a recursive solution [inorder traversal] takes an implicit stack space ? Please correct me if I am wrong ? @Rahul Can you please send us the *morris inorder pdf* link that u have shared once ? Best Regards Kaushik -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST
@Divya I think your solution is correct. To do in constant time , we
can use BST itself instead of storing in array.
Have two array , make first point to left most , make second point to
right most member, now start your algorithm while making
these two pointers move. Left pointer should move in 'inorder' style
while right pointer should move in 'reverse inorder style'
if ( *LeftPtr + * RightPtr k ) Decrement ( RightPtr)
if ( *LeftPtr + * RightPtr k ) Increment (LeftPtr)
else WeHaveAnswer
-Manish
On May 15, 6:49 am, Yalla Sridhar sridhar2...@gmail.com wrote:
if the tree has parent pointer then we can apply similar approach,,
increment and decrenent... and can also be done in O(1)
have to poninters pointed to the min and max nodes and them move pointers by
checking the sums..
On Fri, May 14, 2010 at 5:03 PM, anna thomas annathoma...@gmail.com wrote:
@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
req sum, increment the 1st ptr(ptr at beginning of array). If sum req sum,
then decrement the 2nd ptr(ptr at end of array)
In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum 6)
dec ptr2 1+4 = 5 (sum 6)
inc ptr2: 2+4 =6 (got the ans)
But the qs mentions that it should be in O(1) space.
Regards,
Anna
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries sum, we
should start with the smallest element
and scan the elements from last till we get some value x which together
with the smallest value sums to sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 3:51 PM, Prashant K
prashant.r.k...@gmail.comwrote:
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - ith number (node)
3) now search for 'y' in BST if we found then there is node such that s=
x + y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana Sukhino Bhavanthu ||
On Fri, May 14, 2010 at 2:47 AM, divya jain
sweetdivya@gmail.comwrote:
form a sorted array from inorder traversal of tree. now take to
pointers one to the beginning of array and other at the end. now check if
the sum of element is greater than reqd sum then increment 1st ptr. if
their
sum is less than reqd sum then decrement 2nd ptr. if their sum is equal
to
the reqd sum then this is the ans..
hope it will work..
On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a bst... find two nodes whose sum is equal to a number k ... in
O(n) time and constant space...
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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] Re: BST
sorry , there was a typo
'Have two array read it as Have two pointers
-Manish
On May 16, 1:04 pm, Modeling Expert cs.modelingexp...@gmail.com
wrote:
@Divya I think your solution is correct. To do in constant time , we
can use BST itself instead of storing in array.
Have two array , make first point to left most , make second point to
right most member, now start your algorithm while making
these two pointers move. Left pointer should move in 'inorder' style
while right pointer should move in 'reverse inorder style'
if ( *LeftPtr + * RightPtr k ) Decrement ( RightPtr)
if ( *LeftPtr + * RightPtr k ) Increment (LeftPtr)
else WeHaveAnswer
-Manish
On May 15, 6:49 am, Yalla Sridhar sridhar2...@gmail.com wrote:
if the tree has parent pointer then we can apply similar approach,,
increment and decrenent... and can also be done in O(1)
have to poninters pointed to the min and max nodes and them move pointers by
checking the sums..
On Fri, May 14, 2010 at 5:03 PM, anna thomas annathoma...@gmail.com wrote:
@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
req sum, increment the 1st ptr(ptr at beginning of array). If sum req
sum,
then decrement the 2nd ptr(ptr at end of array)
In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum 6)
dec ptr2 1+4 = 5 (sum 6)
inc ptr2: 2+4 =6 (got the ans)
But the qs mentions that it should be in O(1) space.
Regards,
Anna
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries sum, we
should start with the smallest element
and scan the elements from last till we get some value x which together
with the smallest value sums to sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 3:51 PM, Prashant K
prashant.r.k...@gmail.comwrote:
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - ith number (node)
3) now search for 'y' in BST if we found then there is node such that s=
x + y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana Sukhino Bhavanthu ||
On Fri, May 14, 2010 at 2:47 AM, divya jain
sweetdivya@gmail.comwrote:
form a sorted array from inorder traversal of tree. now take to
pointers one to the beginning of array and other at the end. now check
if
the sum of element is greater than reqd sum then increment 1st ptr. if
their
sum is less than reqd sum then decrement 2nd ptr. if their sum is
equal to
the reqd sum then this is the ans..
hope it will work..
On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a bst... find two nodes whose sum is equal to a number k ... in
O(n) time and constant space...
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
[algogeeks] Re: BST
If you need an array large enough to hold all tree elements, that is not constant space, it is O(n) space. On May 14, 5:47 am, divya jain sweetdivya@gmail.com wrote: form a sorted array from inorder traversal of tree. now take to pointers one to the beginning of array and other at the end. now check if the sum of element is greater than reqd sum then increment 1st ptr. if their sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd sum then this is the ans.. hope it will work.. On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: given a bst... find two nodes whose sum is equal to a number k ... in O(n) time and constant space... -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://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 algoge...@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: BST
Are the node values unsigned? When you say constant space, are you counting call stack space? On May 13, 10:41 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: given a bst... find two nodes whose sum is equal to a number k ... in O(n) time and constant space... -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://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 algoge...@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: BST
with order of n space , we can easily do.. just copy inorder traversal in array.. keep two pointers one at beg and 1 at end increment and decrement accordingly until two pointers meet... but how to do in constant space and O(n) ?? On Fri, May 14, 2010 at 11:17 PM, W Karas wka...@yahoo.com wrote: If you need an array large enough to hold all tree elements, that is not constant space, it is O(n) space. On May 14, 5:47 am, divya jain sweetdivya@gmail.com wrote: form a sorted array from inorder traversal of tree. now take to pointers one to the beginning of array and other at the end. now check if the sum of element is greater than reqd sum then increment 1st ptr. if their sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd sum then this is the ans.. hope it will work.. On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: given a bst... find two nodes whose sum is equal to a number k ... in O(n) time and constant space... -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group athttp:// 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: BST represented in array
Karthik, Sorry for this but I still can't understand your program. Can you describe it for me or give an example of how it works. Will it work even in the case of non-complete BST, I mean for every BST? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
Now in the case of non complete BSTs it may run into trouble...I never handled them. It will work for complete BSTs though as it is. Refer to a previous thread in algogeeks where i had posted the thread inplace sorting and look at the solution by atamurad for the explanation. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
An unique BST does exist for such an array if you assume the root to be 1, then automatically you will be able to fix the left and right children of the root and so on. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
hi, U get sorted numbers if u traverse the BST in inorder..so if u traverse the array following inorder u get sorted list and also u visit each index onceso its O(n)... with regards, koushik chitta On 3/24/07, vim [EMAIL PROTECTED] wrote: hi guys plz explain how to sort elements of BST represented using array in o(n) time -- *** 30 years from now it doesn't matter which shoe you wore,which branded jean you wore..what all matters is WHAT YOU HAVE LEARNED AND HOW YOU HAVE USED IT. http://students.iiit.ac.in/~koushik_c --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
#includestdio.h
#includestdlib.h
#includemath.h
#includestring.h
#define MAXN 2000
int a[MAXN];
int cnt = 0;
int log2n;
int n;
void populatetestcase(int i)
{
if(i*2=n) populatetestcase(i*2);
a=++cnt;
if(i*2+1=n) populatetestcase(i*2+1);
}
int calc_x(int i)
{
return (int)log2l((double)i);
}
int calc_m1(int i)
{
return 1 (log2n-calc_x(i)+1);
}
int calc_m2(int i)
{
return i - (1calc_x(i));
}
int main()
{
int i,j,temp,p;
n=(17)-1;
log2n = calc_x(n);
populatetestcase(1);
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
for(i=1; i=n; i++)
{
printf(%d ,a);
}
system(PAUSE);
return 0;
}
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
yes...but you can sort without constant space using the posted algorithm --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
I think your algo uses O(n) space too On Mar 25, 6:50 am, Karthik Singaram L [EMAIL PROTECTED] wrote: yes...but you can sort without constant space using the posted algorithm --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
Sorry, I thought populatetest was part of the solution. I havent run
your code, but it seems not correct and have you tested it before you
posted here?
in your populatetest
a=++cnt;
doesnt it change a[0] only?
I am pretty amazed if you can do constant space. Can you explain your
algo?
On Mar 25, 2:58 pm, Karthik Singaram L [EMAIL PROTECTED]
wrote:
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
On Mar 25, 4:17 pm, leiz [EMAIL PROTECTED] wrote:
Sorry, I thought populatetest was part of the solution. I havent run
your code, but it seems not correct and have you tested it before you
posted here?
in your populatetest
a=++cnt;
it is a syntax error.
*a = ++cnt changes a[0]
my bad
doesnt it change a[0] only?
I am pretty amazed if you can do constant space. Can you explain your
algo?
On Mar 25, 2:58 pm, Karthik Singaram L [EMAIL PROTECTED]
wrote:
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
i am sorry that is a[i] = ++cnt I made a mistake when pasting the code... --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
