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.