<p><a href="https://math.stackexchange.com/questions/415515/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci">The original copy of the question</a> on MSE.</p>

<p>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:</p>

<ul>
<li>The root has label $S$,</li>
<li><p>for each node $x$ in the tree, and label $l$,</p>

<ul>
<li>$x.left.l = x.l_0 + x.l_1$,</li>
<li>$x.right.l = x.l_0 - x.l_1$,</li>
</ul>

<p>where $l_0$ and $l_1$ are the first and second half of the sequence $l$.</p></li>
</ul>

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

<pre>
                 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
</pre>

<p>where the second level is obtain by </p>

<ul>
<li>$(6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8)$,</li>
<li>$(-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7)$.</li>
</ul>

<p>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$.</p>

<p>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?</p>

CC BY-SA 3.0
2013-06-09T21:16:03.407Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) 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
CC BY-SA 3.0
2013-06-09T21:36:39.440Z
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 [math.se]. For information about citing posts here in your paper please see [How will you cite a discussion on this site in your paper?](http://meta.cstheory.stackexchange.com/questions/352/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
CC BY-SA 3.0
2013-06-09T21:42:20.407Z
@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
CC BY-SA 3.0
2013-06-10T00:14:04.247Z
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
<ds.algorithms><ds.data-structures><tree>
Linear time algorithm for computing the labels of leaves in a recursively defined tree
researcher
# Linear time algorithm for computing the labels of leaves in a recursively defined tree

(Asked by: username_0 on 2013-06-09)

The original copy of the question on MSE.
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?

**Tags:** ds.algorithms, ds.data-structures, tree

> **Comments:**
> **username_1**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) 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).  
> **username_1**: 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 [math.se]. For information about citing posts here in your paper please see [How will you cite a discussion on this site in your paper?](http://meta.cstheory.stackexchange.com/questions/352/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.  
> **username_0**: @username_1: 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!  
> **username_2**: 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.  

---

## 0 answers

