Top Coding Interview Question – Solved

Flip Operations A tree of n nodes is an undirected connected graph Hnving (n - 1) edges. Given an undirected tree comprising of tree_nodes number of nodes numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node has an initially binary value (0 or 1) represented by the array initial[], and an expected binary value represented by the array expected[]. The following operation can be performed on the tree any number of times: - Pick a node u and flip its value. Also, flip the value of all the nodes vin the subtree of u if v % 2 = u %2. A node vlies in the subtree of u if ulies on the path from vto root. Flipping the value of a node means flipping its binary value, i.e., from 0 to 1, and vice versa. - The tree is represented by the arrays tree_from[] and tree_to[] where tree_from[i] is connected to tree_to[i]via an edge for 0 ≤ i< tree_nodes - 1. Find the minimum number of operations needed such that the final binary value of each node becomes equal to the array expected[]. Example Consider the following: tree_nodes = 4 initial = [1, 1, 0, 1] expected = [0, 1, 1, 0] tree_from = [0, 0, 1] tree_to = [1, 2, 3] The nodes are labeled <node number> :< value>.