Product of all nodes except for one in Binary Tree

Question

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?

Answer 1

One simple approach: for an internal node $x$, let $P(x)$ denote the product of the integers on the path from the root to $x$, and let $Q(x)$ denote the set of integers obtainable as the product of all but one of the integers on the path from the root to $x$. Now, descend the tree from the root down to the leaves, computing $P(x)$ and $Q(x)$ for each node $x$ as you go. Note that you can compute $P(x),Q(x)$ from $P(w),Q(w)$, where $w$ is the parent of $x$.

The asymptotic worst-case running time will be $O(n^2)$. No algorithm has better worst-case asymptotic running time, as there can be $\Theta(n^2)$ different products that you need to output, so any correct algorithm will need to have worst-case running time at least $\Theta(N^2)$.