# Linear time algorithm for computing the labels of leaves in a recursively defined tree [closed]

Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows:

• The root has label $S$,
• for each node $x$ in the tree, and label $l$,

• $x.left.l = x.l_0 + x.l_1$,
• $x.right.l = x.l_0 - x.l_1$,

where $l_0$ and $l_1$ are the first and second half of the sequence $l$.

For example, if $S=(1,2,3,4,5,6,7,8)$ we have the tree:

                 1, 2, 3, 4, 5, 6, 7, 8
/                      \
6, 8, 10, 12                       -4, -4, -4, -4
/            \                      /             \
16, 20       -4, -4                -8, -8,         0, 0
/    \       /    \                /     \        /    \
36    -4    -8      0             -16      0      0      0


where the second level is obtain by

• $(6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8)$,
• $(-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7)$.

The problem is to compute the labels for the leaves. In the example, the labels for the leaves are: $36, -4, -8, 0, -16, 0, 0, 0$.

If I compute the tree recursively, the computational complexity will be $O(N \log N)$. That is a little slow for the purpose of the algorithm. Is it possible to calculate the labels for the leaves in linear time?

• It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). – Kaveh Jun 9 '13 at 21:16
• I edited your question, I think it should be easier to understand what you are looking for. I would suggest doing the same thing with the copy on Mathematics. For information about citing posts here in your paper please see How will you cite a discussion on this site in your paper?. You can also click on share and select cite to obtain automatically generated bibtex reference for the post. – Kaveh Jun 9 '13 at 21:36
• @Kaveh: Alright, that sounds reasonable. I'm new here, so I did not know all the rules yet. This is fine for me. Thank you for the edits also! – researcher Jun 9 '13 at 21:42
• An FYI to future people who stumble upon this: On the Math site, answerers noticed that the problem appears to reduce to the Hadamard transform, so it is unlikely that there is a $\mathcal{O}(N)$ solution. – apnorton Jun 10 '13 at 0:14