Your approach is for a binary tree, but the problem statement does not say anything about it.
On Dec 28, 10:27 am, pacific pacific <pacific4...@gmail.com> wrote: > here is my approach : > > Starting from the root node , > if root node need to have a 1 ... > if root is an and gate : > flips = minflips for left child to have value 1 + minflips for the > right child to have value 1 > else > flips = minimum of ( minflips for left child to have value 1 , minflips > for right child to have value 1) > > For a leaf node , return 0 if the leaf has the value needed else return > INFINITY.Also if at any internal node if it is not possible return INFINITY. > > On Tue, Dec 28, 2010 at 10:06 AM, Anand <anandut2...@gmail.com> wrote: > > @Terence. > > > Could please elaborate your answer. Bottom up level order traversal helps > > to get the final root value but how to use it to find minimum flips needed > > to Obtain the desired root value. > > > On Fri, Dec 24, 2010 at 1:56 AM, Terence <technic....@gmail.com> wrote: > > >> Using the same level order traversal (bottom up), calculating the minimum > >> flips to turn each internal node to given value (0/1). > > >> On 2010-12-24 17:19, bittu wrote: > > >>> Boolean tree problem: > > >>> Each leaf node has a boolean value associated with it, 1 or 0. In > >>> addition, each interior node has either an "AND" or an "OR" gate > >>> associated with it. The value of an "AND" gate node is given by the > >>> logical AND of its two children's values. The value of an "OR" gate > >>> likewise is given by the logical OR of its two children's values. The > >>> value of all of the leaf nodes will be given as input so that the > >>> value of all nodes can be calculated up the tree. > >>> It's easy to find the actual value at the root using level order > >>> traversal and a stack(internal if used recursion). > > >>> Given V as the desired result i.e we want the value calculated at the > >>> root to be V(0 or 1) what is the minimum number of gates flip i.e. AND > >>> to OR or OR to AND be required at internal nodes to achieve that? > > >>> Also for each internal node you have boolean associated which tells > >>> whether the node can be flipped or not. You are not supposed to flip a > >>> non flippable internal node. > > >>> Regards > >>> Shashank Mani Narayan > >>> BIT Mesra > > >> -- > >> 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<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
