> I know that "on line" was not part of the initial spec, but the on line
> algorithm is simpler than some that have been proposed, so I suggest
> looking for it.
I came across this problem (a college senior of mine was asked this
very
question in his Amazon interview).
I settled for the following
[EMAIL PROTECTED] wrote:
> See, the idea is to build a max balanced tree.
> For which, we need to check the height of the tree
> only the first time
There is an "on line" algorithm for this problem. An on line algorithm
does not need to see all the input in advance. In this case, the on
line a
rainix wrote:
>
>
> 1
> /\
>23
> /\ /\
> 4 5 6 7
> /\
> 8 9
> (5)
>
> time cost: 2n, O(n)
> space cost: 3, O(1)
Unfortunately this is not a BST.
--~--~-~--~~~---~--~
rainix wrote:
> let level_head_node(i) is the first node of the level i of the
> perfectly balanced BST
>
> ..
> node node_a = level_head_node(i);// get the first node
> of the levle i
> node node_b = level_head_node(i+1);// get the first node of
> the level i+1
>
rainix wrote:
> let level_head_node(i) is the first node of the level i of the
> perfectly balanced BST
>
> ..
> node node_a = level_head_node(i);// get the first node
> of the levle i
> node node_b = level_head_node(i+1);// get the first node of
> the level i+1
>
Another solution
node *oldtree;
node *build_new(N)
{
node *temp, *r;
int N1, N2;
if N==0 return NULL;
N1 = (N-1)/2; //no of node in the right subtree
N2 = N-1-N1; //no of node in the left subtree
temp = build_new(N1);
r = oldtree;
oldtree = oldtree->left;
r->right = temp;
r->left = build_ne
@rajiv..
can you plz write the code or pseducode? i am not clear yet..
thanx in advance
On 3/19/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
> No, I guess you've misunderstood the logic.
>
> See, the idea is to build a max balanced tree.
> For which, we need to check the height of the tree
No, I guess you've misunderstood the logic.
See, the idea is to build a max balanced tree.
For which, we need to check the height of the tree
only the first time, there after we know what
the lengths of the left and right chains are
going to be.
So, though your recursive formula looks right,
>
@rajiv...
everything is right. but i think there is small problem. in order to
get the middle point of the chain you will need to traverse half of
the chain. this will take linear time. so effectively it becomes
T(N) = 2T(N/2) + O(N) which results T(N) = O(NlogN)
plz check whether i am right
O
"Most importantly, I am not convinced about the correctness of the algorithm."
yes i thought it nefore. there is one problem with my method. my
method only ensures that the height of the new tree will be <=
ceiling(log(N+1)). but it is not perfectly balanced. it is possible to
have tree with only
thts not true
first of all n is height of the new tree i.e. ceiling[log(N+1)] where
N is the no. of node in the old tree.
N <= 2^n - 1
and T(n) = T(n-1) + T(n-2) + .. + T(0) + cn
T(n-1) = T(n-2) + ... + T(0) + c(n-1)
so T(n) = 2T(n-2) + 2T(n-3) + .. + 2T(0) + cn + c(n-1)
T(n-2) =
Hi Malay,
I don't see how you algorithm takes O(n) time or O(logn) space, The use of recursion should take into account the implicit stack.
for(int i = 0; i < n; i++)
process(height - 1)
itself transforms into recurrence T(n) = nT(n - 1) + O(1)
You will see that this is exponential (forget
I think the problem can be solved using
tree rotations.
So, we start with a left skewed tree
32
// \
2--->1 3
/
1
Find out the total number of nodes initially,
can be done in O(n) time and O(1) space.
Once we know th
node *root;
node * build(int height)
{
node *r, *temp;
for(i=1, r=null; i<=height && root; i++)
{
temp = root;
root=root->left;
temp->right=r;
r=temp;
r->left = build(i-1);
}
return r;
}
void main()
{
node *tree;
//root contains original tree
tree = buld(n); // n=height of of new tree
}
i will
Malay, I think your solution gives wrong results. Can you please verify
and explain us.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googleg
see my solution it will take logN space and O(N) time
On 3/15/06, pramod <[EMAIL PROTECTED]> wrote:
>
> But this will require O(N) space anyway. The problem asks for O(log(n))
> space.
>
>
>
>
--~--~-~--~~~---~--~~
You received this message because you are subscri
let level_head_node(i) is the first node of the level i of the
perfectly balanced BST
..
node node_a = level_head_node(i);// get the first node
of the levle i
node node_b = level_head_node(i+1);// get the first node of
the level i+1
node tail = cursor_a->left;
But this will require O(N) space anyway. The problem asks for O(log(n))
space.
--~--~-~--~~~---~--~~
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
calculating total no of nodes is too easy... a single traverse through
the tree will suffice... this will take linear time and hence will not
increase runtime complexity
On 3/14/06, BiGYaN <[EMAIL PROTECTED]> wrote:
>
> If we can have the total no. of nodes in tree as an input (say N), this
>
If we can have the total no. of nodes in tree as an input (say N), this
problem is pretty easy.
We construct a full BST of level = ceiling ( log (base 2) N ) - 1
conatining only dummy nodes. Now we travel the BST in the same fashion
as a linked list starting from the root node. The root must hav
node *root;
node * build(int height)
{
node *r, *temp;
for(i=1, r=null; i<=height && root; i++)
{
temp = root;
root=root->left;
temp->right=r;
r=temp;
r->left = build(i-1);
}
return r;
}
void main()
{
node *tree;
tree = buld(n); // n=height of of new tree
}
i think this will take O(N) time and
Sorry. This takes O(n) space, too for an indexable array.
There is so far as I know no "quick and dirty" way of combining simple
algorithms or ideas to get this. You need to come up with an original
algorithm.
--~--~-~--~~~---~--~~
You received this message bec
assign index numbers 1..N to each node
let X = 2^i + k*2^i
node X has (X +/- 2^(i-1)) as its children
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to alg
Madan, yours will take O(n) space.
I could think of an algo which takes O(nlogn) time and O(logn) space.
We first traverse till the middle of the original BST and make it the
root. We also make the till now traversed portion of the tree to be the
right child of this root and then we recursively so
You can convert BST to doubly linkedlist in O(n), convert it into an
array containing corresponding nodes of tree and then to a BST.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post t
25 matches
Mail list logo
