Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node omitted. I am looking for a solution without divisions (i.e. integers can be zero).
One way to go about this I thought of is I can compute all possible partial products starting at the root. That is each node stores the product of the unique path from the root up this node ( but except the integer stored at that particular value ). Then for each leaf node I can walk up the path to the root node multiplying the integers on the way. At a given node before accumulating the node into the product I can multiply the product with the prefix product stored in the node.
It feels like I am doing a lot of redundant multiplications when visiting each path from a leaf to the root, since these paths potentially share a lot of nodes. Is there a way faster way to do this?