Sorry my mistake! But the general problem with more than 2 children possible is more interesting! :)
On Dec 28, 10:58 am, Terence <technic....@gmail.com> wrote: > The description on internal nodes indicates this: > > > 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. > > On 2010-12-28 13:35, suhash wrote: > > > > > > > > > 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.
