Prove that if $\quad\max\{\text{size(t.left),size(t.right)\}}\leqslant 2/3\text{ size(t)}\}$ than the height of T is $O(\log n)$

Question

Given the following definition of binary search tree:

$$\text{size}(t)=\cases{0\qquad\qquad\qquad\qquad\qquad\qquad t=\text{ null}\\ 1+\text{size(t.left)+size(t.right)}\qquad\text{otherwise}}$$

for each vertex in the tree t.size contain the size of it's subtree

Prove that if $\quad\max\{\text{size(t.left),size(t.right)\}}\leqslant 2/3\text{ size(t)}\}$

than the height of T is $O(\log n)$ if it is given that $n=\text{size(T)}$

---

Attempt:

I discovered that the size of a vertex is the number of vertices that there are in the specific root:

e.g:

                              V_1
                             /   \
                           V_2    V_3
                           /      / \
                         V_4     V_5 V_6

The size of $V_4,V_5,V_6$ is: $1+0=1$

The size of $V_2$ is: $1+1=2$

The size of $V_3$ is: $1+1+1=3$

The size of $V_1$ is: $1+3+2=6$

But how can I prove about T's height

Answer 1

In this tree, when you go from one tree to a child tree, no matter what the number of nodes in the new tree is at most $2/3$ the number of nodes in the parent tree. How many times can you multiply $n$ by $2/3$ before it is less than or equal to $1$? Well:

$$n (2/3)^k = 1 \\ k = -\ln(n)/\ln(2/3)$$

So in particular the height of the tree is at most $-\ln(n)/\ln(2/3)+1$. (The $+1$ comes about because I assume a singleton tree has height $1$).

Answer 2

The height of $T$ is also known as the depth and is defined by the maximum number of nodes covered in the longest past from the root node to a leaf node.

In a perfect binary tree the maximum nodes is obtained by $\sum_{k=0}^{h}2^k$ where $h$ is the height of $T$. Since $\sum_{k=0}^{h}2^k=2^{h+1}-1$ then $2^k-1<Size(T)\leq2^{k+1}-1$.

Therefore if $n=Size(T)$ then $\log(2^k-1)<\log(n)\leq\log(2^{k+1}-1)$ thus $\log(2^k-1)<k<\log(2^{k+1}-1)$ then we conclude that $k$ can be obtained as $k=\log(n)$