#includestdio.h
#includeconio.h
#includestdlib.h
int dim,arr[5][5];
int curr_best[6]={-1,-1,-1,-1,-1,-1},x[5]={-1,-1,-1,-1};
void estimate(int,int,int[4]);
void build(int);
// x[k] will contain the choices till now for the current series
// the best soln till now is in curr_best[last] has the
i think u mean lowest commen ancestor?
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.comwrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
Following are the recurrences:
T(n)=2T(n/2)+1
T(2)=1
T(n)=n-1
=O(n)
1 is added because winner of both the sides will compete at most 1 once.
for Time table u can form a tree
x1 x2 x3 x4 x5
\ / \ / /
x1 x3 /
\ \ /
\ x5
\ /
x1
Here are
@atul it is not a BST
On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are greater than current node then traverse node-right
2. if both are
You 've got n teams and nC2 ways of conducting the matches with specified
constraints
that's n/2(n-1). So, each day you need to conduct n/2 matches such that, no
team repeats within a day, no match that was previously held repeats. Since
the problem has an unique solution, you can either brute
Dear Himanshu,
Here is what I think. This problem can be solved easily by using recursion.
Here is the pseudo code for it:
Logic: Let 'A' and 'B' be the given too node whose common ancestor we have
to find. Now perform an inorder traversal of the tree and at every node call
the 'search(A)'
Well Atul, Mind it, its not a Binary Search Tree, its just a Binary Tree. So
this concept of the elements in left sub tree all having the value less than
the current node and similar for the right subtree will not stand here.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8,
yup atul algo is correct
(cur_data - node-right) * ( cur_data- node-left) -1 for ancestors
On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are
Apologizes .. I miss read the question.
On Thu, Apr 8, 2010 at 12:14 PM, vivek bijlwan viv...@gmail.com wrote:
@atul it is not a BST
On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current
@Anurag.
I like your algorithm, but observe some deficiencies...
A could be on the right subtree and B on the left, as well.
And what if B is a descendent of A. Should we consider A to be the
lowest common ancestor (i.e., is a node an ancestor of itself?), or is
the LCA the first ancestor of A?
@ ashish .. each team should play the other team at least once.
in merging that thing does not happen.
On Thu, Apr 8, 2010 at 9:42 AM, Ashish Mishra amishra@gmail.com wrote:
Can it be done in more or less like merge sort way
i.e 1. divide array into half
2. keep on doing it till u
@Dave,
Thanks for pointing out the limitation in my algorithm. I myself realized
the same mistake after I posted the algorithm. You are right, we should
additionally check the presence of A and B on the either side. It will add
few extra conditions to the algorithm. I will soon update the same on
Suppose n=2^k, a(0), a(1), ..., a(n-1) are the n teams
1. If there are 1 team, then no matches, 0 days needed;
If there are 2 teams, arrange 1 match for them, 1day needed.
2. Split the n teams into 2 groups of equal size, ie.
a(0),a(1),...,a(n/2-1) and a(n/2),a(n/2+1),...,a(n-1).
3.
Perform inorder traverse for both the node. match element by element the 2
strings and when first time the string deviates thats Lowest common
ancestor.
-rahul
On Thu, Apr 8, 2010 at 6:21 PM, Anurag Sharma anuragvic...@gmail.comwrote:
@Dave,
Thanks for pointing out the limitation in my
@Rahul,
The Tree is not Binary Search Tree.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 6:52 PM, Rahul Singh rahu...@gmail.com wrote:
Perform inorder traverse for both the node. match element by element the 2
strings and when first time the string deviates
depending upon the situation if you have to find the youngest ancestor
once then what rahul singh can be done
if the situation is you have mutliple query then do it in the following way
preprocessing : make a reversed tree eg
ABC
/ \
For a binary tree , if we are given an inorder traversal and a
preorder/postorder/level-order traversal, we can always reconstruct back the
binary tree. This technique can be used to save and restore the binary tree
efficiently.
I have read that it is necessary to have an inorder traversal to
I know this is not a BST , in BST you do not have to inorder traversal it is
even shorter. You start from root and first instance when node1
currentNode node 2 (or vice versa)you are done .
In case of normal binary tree. you just need to traverse till node1 and then
similarly for node2 . Now
why only Preorder and Postorder is not suffice.
consider Two Binary Tree
Root = A
Left Chid = B
Preorder: A,B
Postorder: B,A
and
Root = A
Right Child = B
Preorder: ,A,B
Postorder: B,A
for given preorder and postorder two different binary trees can be formed
Thanks
Pramod Negi
On Thu, Apr
19 matches
Mail list logo
