1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How do you know that you have a lot of redundant multiplications? Have you tried comparing the complexity of your algorithm to the size of the output? $\endgroup$ – Yuval Filmus Jun 8 at 10:46
  • $\begingroup$ E.g. if the tree looks like a -> b -> c -> d (->e,->f) [a,b,c have degree 1, d has degree 2, e,f are leafs] most of the multiplications are redundant(when traversing paths from leafs to the root). Its true that the output has the same size as the number of multiplication done when traversing every leaf root path, nevertheless in my case multiplications are expensive so I am looking for a way to reduce the number of multiplications. $\endgroup$ – user3726947 Jun 8 at 11:14
  • $\begingroup$ Is it important that there be no divisions? Would a solution using divisions which can handle zero values be good enough? $\endgroup$ – Yuval Filmus Jun 8 at 11:19
  • $\begingroup$ Would a similar problem occur in the complete binary tree? In other words, does the inefficiency stem just from nodes having one children? In this case, some "compression" might be useful. $\endgroup$ – Yuval Filmus Jun 8 at 11:22
  • $\begingroup$ For my application a solution with divisions is ok (never the less I find the problem only using multiplications interesting for its own sake). If the binary tree is complete, consider two leaf nodes with the same parent node. If the depth is say 10 it would be a lot cheaper to first compute the partial products starting from the parent node, mulitplying them with the stored product in the nodes and then mulitplying with either of the leaf nodes. $\endgroup$ – user3726947 Jun 8 at 11:37
2
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.