For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

Question

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}$.

1. Does it work for every binary tree or only when $n$ is divisible by three?
2. How can I quickly prove the fact in my note? A simple idea?

Answer 1

$\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 k<n/3$ or $\ge2k+1>2n/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)<2n/3$ works if $n\equiv0,2\pmod3$. It also works for all $n$ if the tree is full:

Corollary 4: Every binary tree of size $n>1$ such that all nodes have $0$ or $2$ children has a node $u$ such that $n/3\le\s(u)<2n/3$.

Proof: In this case, the size of every subtree (including $n$ itself) is odd. By Corollary 2, there is $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}<2n/3$. If $\f{(n+1)/3}\ge n/3$, we are done. The remaining case is that $\f{(n+1)/3}=(n-1)/3$. But here $n-1$ is even, hence $(n-1)/3$ is also even, while $\s(u)$ is odd. Thus $\s(u)\ge1+(n-1)/3>n/3$. QED

Answer 2

Let us prove that in a binary tree with $n\gt1$ nodes, there is a node $u$ such that $\frac{n}3\le size(u)\le\frac{2n}3$.

Proof: Run the following algorithm.

1. Let $u$ be the root node of the given binary tree.
2. Check the number of nodes in the left subtree and the right subtree of $u$.
   1. If the number of nodes in the left subtree is between $\frac n3$ and $\frac{2n}3$ inclusive, return the left child node of $u$.
   2. If the number of nodes in the right subtree is between $\frac n3$ and $\frac{2n}3$ inclusive, return the right child node of $u$.
   3. If there are more nodes in the left subtree of $u$, assign the left child node of $u$ to $u$. Otherwise, assign the right child node of $u$ to $u$. Go back to step 2.

We claim that whenever the algorithm is entering step 2, $size(u)\gt\frac{2n}3$.

• The first time when the algorithm is entering step 2, $size(u)=n\gt\frac{2n}3$.

• For the sake of induction, assume that $size(u)\gt \frac{2n}3$ when the algorithm is entering step 2 at some moment. We continue to run the algorithm. If it returns at step 2.1 or 2.2, there is nothing more to prove. Otherwise, the algorithm will be entering step 2.3. Then the number of nodes in each subtree of $u$ is not in $[\frac{n}3, \frac{2n}3]$. (Otherwise, the algorithm must have returned at step 2.1 or step 2.2.)

  • If there are more nodes in the left subtree of $u$, the number of nodes in the right subtree of $u$ must be $\le\frac{size(u)}2\le \frac{n}2$. So, the number of nodes in the right subtree of $u$ must be $\lt\frac{n}3$. So the number of nodes in the left subtree $u$ must be $\ge size(u)- \frac{n}3>\frac{n}3.$ That means, the number of nodes in the left subtree $u$ must be $\gt\frac{2n}3$.
  • Otherwise, by similar reasoning, the number of nodes in the right subtree of $u$ must be $\gt\frac{2n}3$.

  So, after $u$ is updated at step 2.3, $size(u)>\frac{2n}3$. In other words, when the algorithm is re-entering step 2 the next time, $size(u)>\frac{2n}3$.

The claim is proved.

Note that $size(u)$ decreases by at least 1 whenever $u$ is updated. So $u$ cannot be updated forever. That means the algorithm must stop at some time. The only places it stops is at step 2.1 or step 2.2, where node $u$ such that $\frac{n}3\le size(u)\le\frac{2n}3$ is returned.

---

Here are more directed answers to your questions.

1. The conclusion works for every binary tree has more than one node. It does not work for a binary tree with one node.
2. The simple idea is checking whether one of the child nodes satisfies the condition. If not, then recurse to the subtree that has no less nodes than the other subtree.

Answer 3

It’s not true for trees with 3k+1 nodes. There is supposed to be a subtree with k+1/3 to 2k+2/3 nodes, that is k+1 to 2k nodes. Take a tree starting with only left nodes until we have a subtree of 2n+1, and then both sub trees have size n. The theorem fails. So assume n = 3k or n = 3k+2.

n = 3k: We start with N = root of the tree. As long as N has a subtree with more than 2n/3 nodes, replace N with the root of that subtree. This will end eventually, and at that point the tree with root N has more than 2n/3 nodes, and both subtrees have at most 2n/3 nodes. The tree has at least 2k+1 nodes. If both subtrees had less than n/3 nodes, that’s at most k-1 nodes, subtrees plus node would have at most 2k-1 nodes, less than the 2k+1 required.

n = 3k+2: We start with N = root of the tree. As long as N has a subtree with more than 2n/3 nodes, replace N with the root of that subtree. This will end eventually, and at that point the tree with root N has more than 2n/3 nodes, and both subtrees have at most 2n/3 nodes. The tree has at least 2k+2 nodes. If both subtrees had less than n/3 nodes, that’s at most k nodes, subtrees plus node would have at most 2k+1 nodes, less than the 2k+2 required.

The two subtrees have at most 2n/3 nodes, and don’t both have less than n/3 nodes, so one has between n/3 and 2n/3 nodes.