2
$\begingroup$

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?
$\endgroup$
1
3
$\begingroup$

$\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

$\endgroup$
2
  • $\begingroup$ Yes. Even better: every binary tree has a subtree with size in $[\lfloor n/3\rfloor,\lfloor2n/3\rfloor]$. (Or if you prefer, in $[\lceil n/3\rceil,\lceil2n/3\rceil]$.) $\endgroup$ – Emil Jeřábek Jan 5 at 15:54
  • $\begingroup$ Yes, both are ceilings. $\endgroup$ – Emil Jeřábek Jan 5 at 16:17
2
$\begingroup$

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.
$\endgroup$
12
  • $\begingroup$ If $n$ is divisible by 3, then the conclusion as well as the proof is easier to understand (by setting $n$ to, for example, 3 or 6), simply because $\frac n3$ and $\frac{2n}3$ are integers. $\endgroup$ – John L. Jan 1 at 23:35
  • $\begingroup$ Yes, $n$ should $\gt1$. It is a huge typo of mine to write $n\ge1$ in my first statement. I did mention that the conclusion "does not work for a binary tree with one node". $\endgroup$ – John L. Jan 2 at 15:49
  • $\begingroup$ I had been preparing a totally different proof since 5 hours ago. I will update my answer once it is done. $\endgroup$ – John L. Jan 2 at 21:45
  • $\begingroup$ You asked, "how do you conclude from $\frac n2$ to $\frac n3$ ?" I just wrote before that paragraph, "the number of nodes in each subtree of $u$ is not in $[\frac{n}3, \frac{2n}3]$". So, if that number is $\le n/2$, then it must be $\lt\frac n3$; otherwise, it will be in $[\frac{n}3, \frac{n}2]$, which is contained in $[\frac{n}3, \frac{2n}3]$. $\endgroup$ – John L. Jan 2 at 21:50
  • $\begingroup$ I have to do something else. I will update before tomorrow. $\endgroup$ – John L. Jan 2 at 21:54
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.