Hey Swathi,
The problem does mention any path but refers to "straight" paths along
a root to leaf path. Therefore, a path need not necessarily start from
the root or end with a leaf but should be along the path from the root
to a leaf.
On Nov 25, 4:05 am, Swathi wrote:
> Career cup book questi
unlink each node in original tree in postorder, and insert these nodes in
new bst tree
surender
On Tue, Nov 8, 2011 at 4:48 AM, vikas wrote:
> @ Above
> no need to have another array or nything
> binTreeToBST(node *root)
> {
> if(!root )return;
> node *newRoot;
> binTreeToBSTConv(root, &ne
@ Above
no need to have another array or nything
binTreeToBST(node *root)
{
if(!root )return;
node *newRoot;
binTreeToBSTConv(root, &newRoot);
}
binTreeToBSTConv(node *old, node *new)
{
if(!old ) return;
binTreeToBSTConv(old->left, new);
binTreeToBSTConv(old->r
@mohit: your algo will add assurance that the tree is balanced.. otherwise
ankit's approach is sufficient.
On Sat, Nov 5, 2011 at 8:49 PM, mohit verma wrote:
> another way is : convert binary tree to link list , sort the list and
> using divide and conquer approach create the BST.
>
> From link
another way is : convert binary tree to link list , sort the list and using
divide and conquer approach create the BST.
>From link list to BST : find mid of sorted link list , make it root node
and put left of it to recursive(list,start,mid->prev) and
root->right=recursive(list,mid->next,last);
I think it's the only way as you need to traverse the entire binary
tree to do it.
On Oct 31, 9:45 pm, Ankuj Gupta wrote:
> How to convert a Binary tree to BST ? Naive way is to create each node
> of Binary tree one by one and keep on creating the BST.
--
You received this message because you
Hi,
We can do like this,
int computeXY(Tnode *root,int x,int y)
{
if(root==NULL)
return x;
root->y=y;
int l=computeXY(root->left,x,y-1);
root->x=l+1;
int r=computeXY(root->right,root->x,y-1);
return r;
}
call it as,
computeXY(root,-1,getHeight(root,0)-1);
Thanks
let the nodes are stored in array like
arr[1]
arr[2]
arr[3]
.
.
.
arr[7].
where arr is a structure having int x,int y.
i=1
initally we set the root(i.e arr[i]) x and y = n/2,log(n) respectively
i++
then we iterate in the followin way
while(i<=n)
{
arr[i].x=parent(arr[i]).x-1
arr[i].y=parent(arr[
an improvement to above solution
take a dynamic linear array structure storing ( and y-index) and
whose index tells x value of
Algo:> do inorder traversal and when reach the leftmost end of the tree
start updating the structure.
On Wed, Aug 24, 2011 at 1:53 AM, DK wrote:
> Let Left = -1, R
Let Left = -1, Right = +1
For each node Set:
X = Sigma{Left or Right for each node on the path from root to node}
Y = -Depth of the node in the tree
Go through the tree once and set X and Y values using any traversal (say
postorder) in an array.
Also, during that traversal, find max_height and t
@amit jaspal..I am not able to understand how will u be saving the
nodes for which the largest diameter existsI know how to find the
largest diameter but the question was to find the nodes too for which
the largest diameter exists...please correct me if I missed something
On 5/30/11, Amit Jasp
@ piyush: u dont need to work with queues, just modify the height
function...
int findDiameter(node *root,int *p){
printf("hi\n");
//if(root->left==NULL && root->right==NULL) return 0;
if(root!=NULL){
int l,r;
l=findDiameter(root->left,p);
r=findDia
Dudethe question was to find the two nodes also for which the
maximum distance exists.in ur code there is nothing as
suchkindly read the question carefully before posting...
On 5/31/11, bittu wrote:
> HI All Yes It The Diameter of BT .& Can be done in O(N) after
> optimization
> have
Right!! that is pretty standard problem but the solution u have given
is for undirected graphs and intuitively binary trees are directed.
Piyush solution will work for binary tree.
On May 30, 2:04 am, anshu mishra wrote:
> this is a very standard problem :D
>
> start with any node(x) find the nod
nope, it will not work :(
got a case
On Mon, May 30, 2011 at 11:57 PM, sunny agrawal wrote:
> won't this simple algo work ??
>
> start from root node, say it has value 0
> at any time if a node has a value v
> pass v-1 to left subtree and v+1 to right subtree
> keep track of max and min
> final a
won't this simple algo work ??
start from root node, say it has value 0
at any time if a node has a value v
pass v-1 to left subtree and v+1 to right subtree
keep track of max and min
final answer will be max -min = Diameter of tree.
correct me if i m wrong.
--
You received this message because
I think following algo will work..I haven't tested it plus its in its crude
form...Kindly correct me if i am wrong..
*typedef struct queue
{
struct node *q[2];
int h1,h2;
}queue;*
**
*queue max_dist(struct node * tree)
{
if (tree == NULL)
return;
queue q1,q2,q3;
q1.h1 = heig
little modification
start with any node(r) find the node(x) which is at maximum distance.
--
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 em
this is a very standard problem :D
start with any node(x) find the node which is at maximum distance.
now start with x travese the tree and find the node(y) which is at maximum
distance.
so finally answer wil be (x, y)
traversing the tree two times. so the order for finiding the such nodes
equa
@ross...I think it can be done by taking a queue/stack...I am working on the
code...Please comment if there is any error in my approach..
On Mon, May 30, 2011 at 2:19 PM, Maksym Melnychok wrote:
> simplest algo: find a node with max depth M and go up tree calculating max
> depth of all upper br
simplest algo: find a node with max depth M and go up tree calculating max
depth of all upper branches that do not contain M until reaching root node
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge
@piyush,
Hi, thanks alot for the solution,
Thats to find the diameter of a tree. :)
But, how would you obtain the 2 nodes which have the max. distance
betwn them?
On May 30, 1:17 pm, Vipul Kumar wrote:
> That is same as finding the diameter of the tree.
>
>
>
>
>
>
>
> On Mon, May 30, 2011 at 1
what is rmq
On Fri, Mar 4, 2011 at 7:21 AM, Vipin Agrawal wrote:
> There are many way to find out least common ancestor.
> Best Solution is RMQ.
>
> On Mar 4, 3:59 pm, Sudhir mishra wrote:
> > binary tree, nodes, each node has an ID
> >
> > root node of the tree
> >
> > structure node{
> >
> >
There are many way to find out least common ancestor.
Best Solution is RMQ.
On Mar 4, 3:59 pm, Sudhir mishra wrote:
> binary tree, nodes, each node has an ID
>
> root node of the tree
>
> structure node{
>
> int id;
>
> node *left;
>
> node *right;}
>
> - problem: given
@all why you wants to change the tree structure do you know they don't
allow that otherwise it wont be amazon question
we can use Array as data Structure vertical sum in that as what jalaj
told
in case you wants to see working code check out \
http://shashank7s.blogspot.com/2011/02/wap-to-findo
My implementation tries to create a doubly linked list, each node of
which will hold the value of sum of all nodes in a particular
vertical.If there is no requirement for the final output to state
vertical number against the sum (and indeed there is no such
requirement in the question ), then my ap
hash would be a perfect choice.
I make a MinMaxHash class which would keep track of the min and max
value of the key.(since in this case we would never remove a key, thus
this primitive approach works. Otherwise use treeMap)
class MinMaxHash extends HashMap{
private Integer min = Integer.MAX_
Just a slight addition , you would also like to keep a record for the
maximum range of the levels (assuming the function is called as
(root , 0))
On Feb 14, 5:25 pm, jalaj jaiswal wrote:
> use hash
>
> take an array verticalsum[]={0};
>
> the function will be like this
> void vertcal_sum(node *r
Just dfs for the left subtree and log all events (left, right childs and
elements) - use stack for this.
Then do the same for the right subtree, but check events in a reverse (left
child event should be right child).
If there are no differencies, so right subtree is an exact mirrot of the
left o
We can do the following.
We associate a variable with each of the node. let it be called level.
We now do BFS on the tree. Whenever we visit a node we do the
following:
node.level = blackNeigbor.level + 1.
Now we again do a BFS to find the number of nodes in each level.
--
You received this me
@Ankit- I think it can be done using a single queue also.
2010/10/23 ankit agarwal
> Do level order traversal using two queues.
>
>
> On Oct 23, 8:19 pm, "juver++" wrote:
> > When visiting appropriate vertex v, increment counter +
> > +levels[current_depth] and go further.
> > You may done this
Do level order traversal using two queues.
On Oct 23, 8:19 pm, "juver++" wrote:
> When visiting appropriate vertex v, increment counter +
> +levels[current_depth] and go further.
> You may done this using DFS or BFS.
>
> On 23 окт, 17:31, Harshal wrote:
>
>
>
>
>
>
>
> > hi, i need to find the
When visiting appropriate vertex v, increment counter +
+levels[current_depth] and go further.
You may done this using DFS or BFS.
On 23 окт, 17:31, Harshal wrote:
> hi, i need to find the number of nodes at each level of a binary tree..the
> binary tree may not be balanced..
>
> output:
> Level
do BFS.
On Oct 23, 6:31 pm, Harshal wrote:
> hi, i need to find the number of nodes at each level of a binary tree..the
> binary tree may not be balanced..
>
> output:
> Level 0 - 1 node
> Level 1 - 2 nodes
> Level 2- 3 nodes
>
> and so on..based on the tree structure..I am not able to count at
@Amit - could u explain this with an example??
Do u mean the root node after inverting will have all the nodes to one
side??
--
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 u
@albert:
itz enough to make the right pointer to point to the next node.. no
need that left should point to the previous node..
On Aug 30, 8:14 am, Chonku wrote:
> @albert
> I am not forming a separate list. My assumption was that next pointer is
> present in the node. But I will try to post a so
@albert
I am not forming a separate list. My assumption was that next pointer is
present in the node. But I will try to post a solution with only left and
right pointers.
On Mon, Aug 30, 2010 at 12:10 AM, albert theboss wrote:
> @Chonku:
>
> you cant use "next" pointer in that...
>
> you have to
@Chonku:
you cant use "next" pointer in that...
you have to make link list such that right ptr points to next node
and left pointer to prev node
Am i right???
correct me if i am wrong.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" grou
Made some changes.
flattenTree(TreeNode node,TreeNode previous) {
if (node is leaf) {
previous = node
return;
}
flattenTree(node->left,previous);
if (previous != null) {
previous->next = node;
previous=node;
}
flattenTree(node->right,previous);
@Chonku:
yours is wrong. consider the given ex,.
50
/ \
25 60
/ \ / \
5 30 55 75
5 will become head. 5->next=25. 25->next=30. then 25 will be returned
up.
so 25->next=50. which is wrong
On Aug 26, 11:36 pm, Chonku wrote:
> At first, store the pointer to the
I think a solution to convert a Binary Tree to a Doubly Linked List
has been discussed!
On Aug 27, 9:32 pm, balashankar sundar wrote:
> head=new node;//head node to list,T is root to the tree
> join=head;//global variable
>
> inorder(T)
> {
> if(T==0)
> return;
> inorder(t->l)
head=new node;//head node to list,T is root to the tree
join=head;//global variable
inorder(T)
{
if(T==0)
return;
inorder(t->l);
join->l=T;
join=join->l;
inorder(T->r);
}
head=head->l;
end;
On Aug 26, 10:57 pm, Rahul wrote:
> how to rearrange the pointers ??
--
You receiv
how to rearrange the 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
On May 23, 2:25 am, Vinodh <[EMAIL PROTECTED]> wrote:
> For traversing binary trees there are standard ways like,
> - In order
> - Pre Order
> - Post Order
>
> Questions Are:
> The construction of the data as a binary tree is upto us. Am I right?
> (I read somewhere 2n-n combinations are possib
The thing that you asked for is formally known as BFT (Breadth First
Traversal). Here's the pseudo-code that'll give you the idea in
general.
#define MAX 100
void BFT ( node *root )
{
node *p;
ins_Q(root);// inserting the node into a queue
do
{
Hi
This is the basic breadth first search algo. We can use a queue to achieve
such a traversal.
Check this out : http://en.wikipedia.org/wiki/Breadth-first_search
--
Aravind Narayanan
[EMAIL PROTECTED]
On 4/29/07, misty <[EMAIL PROTECTED]> wrote:
>
>
> hi friends
> I want to know ,how to write
thanks!
On 3/7/07, Jair Cazarin <[EMAIL PROTECTED]> wrote:
>
> That's a conditional expression. Check google.
>
> On 3/6/07, Lukas alkauskas <[EMAIL PROTECTED]> wrote:
>
> > BTW where i can find this kind "(lheight > rheight ? lheight : rheight)"
> > syntax tutorial or smth ?
> >
> > On 3/6/07, N
That's a conditional expression. Check google.
On 3/6/07, Lukas alkauskas <[EMAIL PROTECTED]> wrote:
>
> BTW where i can find this kind "(lheight > rheight ? lheight : rheight)"
> syntax tutorial or smth ?
>
> On 3/6/07, Nat (Padmanabhan Natarajan) < [EMAIL PROTECTED]> wrote:
> >
> > The system u
BTW where i can find this kind "(lheight > rheight ? lheight : rheight)"
syntax tutorial or smth ?
On 3/6/07, Nat (Padmanabhan Natarajan) <[EMAIL PROTECTED]> wrote:
>
> The system uses only one stack to implement recursion, so you should be
> able to do it too :-)
>
> On 3/6/07, NUPUL < [EMAIL PRO
The system uses only one stack to implement recursion, so you should be able
to do it too :-)
On 3/6/07, NUPUL <[EMAIL PROTECTED]> wrote:
>
>
>
>
> On Feb 28, 8:06 pm, "k3xji" <[EMAIL PROTECTED]> wrote:
>
> > Is there any way of calculating the depth of a binary tree without
> > using *recursive w
On Feb 28, 8:06 pm, "k3xji" <[EMAIL PROTECTED]> wrote:
> Is there any way of calculating the depth of a binary tree without
> using *recursive way*.Also not using *log2-1* method.I am asking this
> because Is there any way of doing this kind of operation with just
> using stacks or quenes.
Yes
Thats correct.On 10/27/06, arun kumar manickan <[EMAIL PROTECTED]> wrote:
DFS on a BST = it pre order traversal ..
is this correct ?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To pos
DFS on a BST = it pre order traversal ..
is this correct ?
--~--~-~--~~~---~--~~
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 fro
draw a trivial tree.
Traverse it 'in-order'. Do a DFS.
See if you get the same result.
Don't underestimate the power of paper and thought.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To
NO
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more op
55 matches
Mail list logo
