@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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
