@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.
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
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
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
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;
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
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
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
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
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
@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
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
@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
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
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
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
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
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
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
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
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
@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
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.
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
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
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
@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
@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
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
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
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 ||
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
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
@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
@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
@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
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.
--
@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,
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.
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
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.
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:
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
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
@ 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
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
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
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
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.
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
@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
@ 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
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)
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
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-
@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
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
@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
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
@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
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
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.
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
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
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
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.
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
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
#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);
}
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
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
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
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
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
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
75 matches
Mail list logo
