[algogeeks] Re: Building A Special Tree
Taking a Wild Stab at this problem: This is like evaluating a prefix expression. We know that an expression tree also has either 0 or 2 children and the internal nodes are operators and leaf nodes are operands. In a prefix expression we try to look for the pattern operatoroperandoperand. If we find such a thing we evaluate it and put a placeholder for it in the string. Similarly for this, we look for the pattern NXX. where X is either L or a placeholder for a partially constructed tree. Construct the tree and replace in place of NXX a placeholder like L'. Repeat this and you will have a tree. Consider the following tree(Same from above comment) N / \ N N / \ / \ N L N L / \ / \ L L L L Prefix expression is NNNLLLNNLLL 1st NXX pattern is: NN(NLL)LNNLLL construct a tree for it and replace in the String as L' to get NNL'LNNLLL 2nd NXX: N(NL'L)NNLLL =NL'NNLLL 3rd NXX: NL'N(NLL)L = NL'NL'L 4th NXX NL'(NL'L) = NL'L' (Final result) Basically we are constructing the tree in a bottom up fashion. On Jan 14, 10:20 am, Decipher ankurseth...@gmail.com wrote: A special type of tree is given, where all leaf are marked with L and others are marked with N. every node can have 0 or at most 2 nodes. Trees preorder traversal is given give a algorithm to build tree from this traversal. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
Please Try to Correct it Its Showing Segmentation fault...Reply
ASAP...
its code for the above program might be not designed in same
way...what question..asking ..but i tried..itTry to make is Clear
Executable ...
consider tree below
1
/ \
1 0
/ \ / \
1 0 10
/ \ / \
00 00
#include stdio.h
#include stdlib.h
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Given a binary tree, print its nodes in inorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;
/* first print data of node */
printf(%d , node-data);
/* then recur on left sutree */
printPreorder(node-left);
/* now recur on right subtree */
printPreorder(node-right);
}
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node-data = data;
node-left = NULL;
node-right = NULL;
return(node);
}
struct node* build_CBT(struct node *root)
{
struct node *node=root;
if(node==NULL)
{ printf( Special Tree Yes);
return;
}
if(node!=NULL)
{ node-data=newNode(1);
if(node-left ==NULL node-right==NULL)
{ node-left-data=node-right-data=newNode(0);
return;
}
}
else
{
if(node-left!=NULL)
{
//node-left-data=N;
build_CBT(node-left);
}
if(node-right!=NULL)
{
//put(node-right-data=N;
build_CBT(node-right);
}
}
return node;
}
/*Driver program to test above functions*/
int main()
{
/*create a tree*/
struct node *root=(struct node *)malloc(sizeof(struct node)*9);
root=build_CBT(root);
printPreorder(root);
getchar();
return 0;
}
Thanks Regards
Shashank Mani The Best Way To Escape From The Problem is to Solve it
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
@juver++..write ur algo.. i will see that.. Thanks Regards Shashank Mani -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
How we can build a tree with only one traversal ..i think to build a tree atlesat two traversal required e.g N / \ N N / \ / \ N L NL / \ / \ N NN N so preorder is given by NLL Therefore, following combination can uniquely identify a tree. Inorder and Preorder. Inorder and Postorder. Inorder and Level-order. And following do not. Postorder and Preorder. Preorder and Level-order. Postorder and Level-order. This is Very important Question Asked In Amazon Please Have a Closer look at Question... Please let me know any solution exist Thanks Regards Shashank Mani -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
@bittu We have complete binary tree. Preorder information about nodes and leaves is enough. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
@above You create your binary tree from scratch. Where is an input data with preorder labels? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
as i think tree is given as its amazon question N / \ N N / \ / \ N L NL / \ / \ N N N N Regards Shashank Mani -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
It's irrelevant but Building Special Tree has the same acronyms as Binary Search Tree...lame joke I know On Jan 14, 8:44 am, vaibhav agrawal agrvaib...@gmail.com wrote: If it is a BST...then having a pre-order traversal can give us the unique binary tree. Also, as per the problem statement, every node can have 0 or at most 2 nodes. that means every node can have 0 or two childs, which is not the case below. On Fri, Jan 14, 2011 at 6:49 PM, Balaji Ramani rbalaji.psgt...@gmail.comwrote: Two different binary trees can have same set of Leaves/Inner Nodes and same Preorder traversal 5 / \ 3 10 / \ 1 9 \ 7 5 / \ 3 9 / / \ 1 7 10 So, I guess it is not solvable unless we have some more information. Thanks, Balaji. On Fri, Jan 14, 2011 at 10:50 AM, Decipher ankurseth...@gmail.com wrote: A special type of tree is given, where all leaf are marked with L and others are marked with N. every node can have 0 or at most 2 nodes. Trees preorder traversal is given give a algorithm to build tree from this traversal. -- 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 algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
