Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?

Question

Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $a[0]$ and $a[1]$. Each of those nodes have two child nodes $b[0]$ and $b[1]$. Each of those nodes ($b[0]$ and $b[1]$ from both $a[0]$ and $a[1]$) have two child nodes, $c[0]$ and $c[1]$, and so on and so on. To evaluate such a tree, you start at the bottom of the tree, add up the two leaf nodes in each of the last parent nodes, and multiply that by its parent node. This is now the new value of the parent nodes. This process is repeated upwards until you do $a[0](b[0]+b[1])+a[1](b[0]+b[1])$ (remember that $b[0]$ and $b[1]$ are no longer $7$ and $67$, respectively at this point). Can you do this evaluation in polynomial time, in respect to the number of levels of the tree?

Follow up: Can it still be done in polynomial time if some of the leaf nodes are missing?

EDIT: Here is a picture with what I mean:

Answer 1

No. A complete binary tree has $\ell$ levels and about $2^\ell$ nodes. Any algorithm must examine all nodes to get the correct answer, so the running time has to be exponential in the number of levels.

(A small note of caution: "polynomial time" typically means polynomial in the size of the input, so it could risk some confusion to talk about it as "polynomial time" when you mean a polynomial in the number of levels.)