hey,i guess a specific binary tree is not possible...by d use of jst a
preorder...
4 a specific tree inorder is also reqd...
dere will be many trees posible...sso is it dat v got 2 make all possible
tree vth d given preorder???
On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta ankuj2...@gmail.com
this is an O(n^2) solution. By pre processing the array we can also solve it
O(n)
int find_mid(int ar[], int s, int e, int val)
{
int i;
for (i = s; ar[i] val; i++);
return i;
}
node * constructTree(int ar[], int s, int e)
{
node *root;
root = new node();
root-val =
You will also need Inorder traversal data.
On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta ankuj2...@gmail.com wrote:
How to reconstruct a BST from just the prorder traversal of that tree ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
@Anand
As given it is a BST so any single traversal(pre or post or in) is
sufficient to construct the tree. :P
--
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
It turns out preorder is enough if you know it was generated from a
BST. Inorder is needed if it was an arbitrary tree.
One way to code the algorithm is with a stack to hold nodes that
already have a left child and might still need a right one.
// assume: unique keys
// root is the tree we're
As others have said this is not stated precisely. There are lots of
sorting algorithms that have O(n) behavior on nearly sorted
data.Quicksort and mergesort can both be implemented to get this
behavior. However if you are very confident that elements are not very
far from their correct sorted
@Anshu: for a tree
15
15
7 18and
717
17 18
inorder traversal is same: 7,15,17,18
then how it could be possible to recreate the specific one. Preorder of BST
is
This might sound silly. But I have a doubt here.when you mean convert inorder
or preorder to a bst. Are the inorder traversel elements given and we need to
construct a bst?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this
Use recursion with the code as follows
void add(node *root, int *sum)
{
}
On Tue, Oct 18, 2011 at 8:58 AM, sravanreddy001 sravanreddy...@gmail.comwrote:
I that is what is suggested in the above code. Even here you can avoid the
sorting and add all with same x coordinate.. O(n) space as
@sravan
yes you are given the sequence of elements in the order in which they are
traversed in the given traversal (in/pre/post)
a BST can be constructed from its post or pre order only but can not be
constructed from only inorder
in case of inorder we also need one more traversal
--
Sunny
On Tue, Oct 18, 2011 at 6:30 PM, sravanreddy001 sravanreddy...@gmail.comwrote:
This might sound silly. But I have a doubt here.when you mean convert
inorder or preorder to a bst. Are the inorder traversel elements given and
we need to construct a bst?
Yes inorder traversal elements are
@rahul can you order your trees properly :(
For BST only preorder traversal is sufficient to reconstruct it back
On Oct 18, 5:58 pm, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@Anshu: for a tree
15
15
7 18 and
7 17
17
On Tue, Oct 18, 2011 at 6:31 PM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
Use recursion with the code as follows
sum array of sums, with horizontal levels, level 0 is for leftmost element
void add(node *root, int *sum, int level)
{
if(root-left)
{
yah i also think that for an BST on preorder traversal is efficient to
construct it again 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
@all Its Obvious ,I Didn't tell for old users or active members , i said for
who are joining or joined recently , so that we can detect easily who is
posting off topic :)
Anyways It Was Just Message , Thread Will be Closed :)
Thanks
Shashank
CSE,BIT Mesra
--
You received this message
Here is some code to study. I should have pointed out that this is
O(n) where n is # of nodes. This leaves out error checking. The
input must be a valid pre-order.
#include stdio.h
#include stdlib.h
typedef struct node_s {
int key;
struct node_s *left, *right;
} NODE;
void
It depends on the language.
If is is a scripted or interpreted language then you can just change
the source code.
If it is a compiled language you would change the binary code where
the output value is stored.
I'm not saying that it is a recommended approach, but it is possible.
Don
On Oct 17,
Not really. Most executable formats have a way to include extra data
that's not used by the loader. You could store a count in such data
and have the program modify the executable every time it runs. Not
recommended, though. A separate file is a much better idea.
You could also play games by
Hi all,
How to find all the anagrams in a large file containing n words and max
length of a word is m letters??
so if file contains add dad abc ced cba it shud say adc dad are anagrams and
abc cba are anagrams.
time needed is 0(nlogn)
--
People often say that motivation doesn't last.
Sort the all the string , Calculate hash-value , if the two has same hash
vale they have to be anagram. put in group on the basis of anagram.
leme know if i missed anything ?
TC O(nlogm) n =number of words m is length of max string
Shashank
CSE,BIT Mesra
--
You received this message because
@Ankur NO Need of Two Array , Only One will be Suffice :)
Just Initialized array with 0 for all nodes initiallly
Thanks
Shashank
CSE,BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Hmm I see but if there are m max letters in each word and there are n words
in the file, then each word sort is O(mlogm) and for n words so wont it be
O(nmlogm)?
On Tue, Oct 18, 2011 at 12:55 PM, WgpShashank shashank7andr...@gmail.comwrote:
Sort the all the string , Calculate hash-value , if
also what would be a suitable hash function for the string?
On Tue, Oct 18, 2011 at 1:21 PM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
Hmm I see but if there are m max letters in each word and there are n words
in the file, then each word sort is O(mlogm) and for n words so wont it be
@Don, Gene:
very good insights,
didn't even thought of the changing the executable, but it indeed is one way
to do.
:)
@Don: agree with scripts and interpreted code.. :)
[coming out of the same language helps answers some questions easily]
--
You received this message because you are
@Sunny, Rahul:
Thanks a lot.. :)
@Anshu: the code is perfect, This would be h = n* (height of BST) -- O(h)
O(n^2) is the worst case right? and has complexity similar to quick sort?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view
It should be O(n.m.log m)
the hash fn choosed here was sorted_char_string -- abc, bac, cba, ... all
result in abc.
how about, (a*b*c)+ (a+b+c) -- it can store the space considerably, if we
use a integer, (just m) instead of log m.
but we need to prove that for any two sets of integers
As per implementation can be done in log(n) using a self balancing
bst.i am not sure but i think that is how c++ maps are
implemented.this wud make the overall complexity o(n*m)+o (n*logn)
though i am not sure if this is correct analysis
On 10/19/11, saurabh singh saurab...@gmail.com wrote:
Sorting can be easily done in o(n) as number of chars will be
small(256) for ascii
On 10/19/11, Arun Vishwanathan aaron.nar...@gmail.com wrote:
also what would be a suitable hash function for the string?
On Tue, Oct 18, 2011 at 1:21 PM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
Hmm I
Can someone give me an idea about how to see the range of segments like data
,heap,stack and text segments of an executable file.(a.out)
Is there anyway to access the those segments from the program itself (while
in execution), like using stack pointer for stack segment ??
On 18 October 2011
@Ravindra
may be the interviewer wants from u that instead of blindly checking for
every number. first check that particular number can be written as the sum
of two squares or not if yes than only search for that number. So the order
will be decrease from O(n^2) to O(n * (number of side which is
30 matches
Mail list logo
