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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
