Return to Question

I want to know if there exists a positive constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for large enough $h$ that is).

I want to know if there exists a positive constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for $h \geq 2$).

I want to know if there exists a positive constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for large enough $h$ that is).

Thanks :)

I want to know if there exists a positive constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for large enough $h$ that is).

I want to know if exists a constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for large enough $h$ that is).

Thanks :)

I want to know if there exists a positive constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for large enough $h$ that is).

Thanks :)