patternMinor
For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes
Viewed 0 times
nodeswithbinaryforsubtreetheretree
Problem
in my notes I have one fact:
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at most $\frac{2n}{3}$.
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at most $\frac{2n}{3}$.
- Does it work for every binary tree or only when $n$ is divisible by three?
- How can I quickly prove the fact in my note? A simple idea?
Solution
$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k2n/3$.
A version suitable for all $n$ can be proved as follows. Let $\s(u)$ denote the size of the subtree rooted at $u$.
Lemma 1: If $1\le s\le n$, then every binary tree of size $n$ has a node $u$ such that $s\le\s(u)\le2s-1$.
Proof: Let $u$ be a node with $\s(u)\ge s$ such that $\s(u)$ is minimal possible. By minimality, the child subtrees of $u$ have size $\le s-1$ each, hence $\s(u)\le2(s-1)+1=2s-1$. QED
Balancing $\s(u)$ and its complement, we obtain the following.
Corollary 2: In every binary tree of size $n>1$,
-
there is a node $u$ such that $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$, and
-
there is a node $u$ such that $\c{n/3}\le\s(u)\le\f{(2n+1)/3}$.
Proof: Using Lemma 1 with $s=\f{(n+1)/3}$, we have $2s-1\le\f{(2n+2)/3}-1=\f{(2n-1)/3}$. Likewise, $2\c{n/3}-1=2\f{(n+2)/3}-1\le\f{(2n+4)/3}-1=\f{(2n+1)/3}$. QED
We can also reformulate it as follows:
Corollary 3: Every binary tree of size $n>1$ has a subtree such that both the subtree and its complement have sizes between $\f{(n+1)/3}$ and $\f{(2n+1)/3}$.
Proof: Taking $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$ by Corollary 2, the complement of the subtree rooted at $u$ has size between $n-\f{(2n-1)/3}=\c{(n+1)/3}=\f{n/3}+1$ and $n-\f{(n+1)/3}=\c{(2n-1)/3}=\f{(2n+1)/3}$. QED
Using Corollary 2, the simple bound $n/3\le\s(u)1$ such that all nodes have $0$ or $2$ children has a node $u$ such that $n/3\le\s(u)n/3$. QED
A version suitable for all $n$ can be proved as follows. Let $\s(u)$ denote the size of the subtree rooted at $u$.
Lemma 1: If $1\le s\le n$, then every binary tree of size $n$ has a node $u$ such that $s\le\s(u)\le2s-1$.
Proof: Let $u$ be a node with $\s(u)\ge s$ such that $\s(u)$ is minimal possible. By minimality, the child subtrees of $u$ have size $\le s-1$ each, hence $\s(u)\le2(s-1)+1=2s-1$. QED
Balancing $\s(u)$ and its complement, we obtain the following.
Corollary 2: In every binary tree of size $n>1$,
-
there is a node $u$ such that $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$, and
-
there is a node $u$ such that $\c{n/3}\le\s(u)\le\f{(2n+1)/3}$.
Proof: Using Lemma 1 with $s=\f{(n+1)/3}$, we have $2s-1\le\f{(2n+2)/3}-1=\f{(2n-1)/3}$. Likewise, $2\c{n/3}-1=2\f{(n+2)/3}-1\le\f{(2n+4)/3}-1=\f{(2n+1)/3}$. QED
We can also reformulate it as follows:
Corollary 3: Every binary tree of size $n>1$ has a subtree such that both the subtree and its complement have sizes between $\f{(n+1)/3}$ and $\f{(2n+1)/3}$.
Proof: Taking $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$ by Corollary 2, the complement of the subtree rooted at $u$ has size between $n-\f{(2n-1)/3}=\c{(n+1)/3}=\f{n/3}+1$ and $n-\f{(n+1)/3}=\c{(2n-1)/3}=\f{(2n+1)/3}$. QED
Using Corollary 2, the simple bound $n/3\le\s(u)1$ such that all nodes have $0$ or $2$ children has a node $u$ such that $n/3\le\s(u)n/3$. QED
Context
StackExchange Computer Science Q#133521, answer score: 5
Revisions (0)
No revisions yet.