Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

Question

I was binary indexed trees and I came across this article. One part of the justification was the following:

Given that the (binary search tree) tree is perfectly balanced, a node N will have exactly $2^{i}-1$ children on each side, where $i$ is the position of the first 1-bit in N, starting from 0, and counting from least significant to most significant. For example, for $N=11000$, we have $i=3$. For $N=111$, we have $i = 0$. This can easily be checked by recalling that the left children of $N$ consist of every number lower than $N$ (similarly for the right side). The “minus 1″ is there because we can’t count $N$ itself as being a child of $N$.

First off, I believe that the authors claim that

"This can easily be checked by recalling that the left children of $N$ consist of every number lower than $N$"

is not entirely accurate, as for example, in the following BBST:

      4
   /     \
  2       6
 / \     / \
1   3   5   7

The left children of node 6 do not contain every number lower than 6. Nevertheless, the formula $2^i - 1$ still holds true. Why does this work?

Answer 1

Since I'm still learning proof techniques, this is a good practice for me too. Please verify the solution yourself. We shall prove this with a series of lemma.

Lemma 1. A perfectly balanced tree with height $h$ would have $n = 2^{h+1}-1$ nodes.

Proof. Trivial proof by induction.

Lemma 2. A perfectly balanced indexed binary search tree have root with value $2^h$.

Proof. By lemma 1, there are $2^h-1$ nodes on the left subtree of the root. By constraint of binary search tree, the root element will have value $(2^h-1)+1=2^h$.

Lemma 3. In a perfectly balanced indexed binary search tree, any node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$ and right child with value $k+2^{h-1}$.

Proof. Due to the properties of the tree, the value of the left child of $A$ is the value of $A$ itself, which is $k$, subtracted by the number of nodes on the right subtree of the left child, which is $2^{h-1}-1$ from lemma 1, added by one. This is trivial upon drawing out such a tree, which I shall not include here. Hence, the value of left child is $k-(2^{h-1}-1)-1=k-2^{h-1}$. A similar proof will suffice for the value of right child.

Theorem. In a perfectly balanced binary search tree with height $h$, any node $A$ will have exactly $2^i−1$ children on each side, where $i$ is the position of the first $1$-bit in the value of node $A$, starting from $0$, and counting from least significant to most significant.

Proof. We shall prove by induction from root down to leaves. By lemma 2, the root value is $2^h$, which binary representation is

$$ 1\overbrace{0\dots0}^h $$

The position of the first $1$-bit will therefore be in the $h$ position. Substituting $i=h$, we have $2^h-1$ children on each side, which agree with lemma 1.

Now, we assume any node $A$ satisfy the stated theorem. By lemma 3, the left child of node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$. By lemma 1, we know that $i=h$, so it suffice to show that the position of the first $1$-bit in $k-2^{h-1}$ appears a bit before that in $k$. In other words, we can assume that the first $1$-bit in $k$ appears at position $h$, and we need to show that the first $1$-bit in $k-2^{h-1}$ appears at position $h-1$.

In binary, we can represent $k$ as

$$ 1\dots1\overbrace{0\dots0}^{h} $$

and we are subtracting it from $2^{h-1}$, as represented by

$$ 1\overbrace{0\dots0}^{h-1} $$

Since $k$ is all zeros in the first $h$ bits, subtracting by $2^{h-1}$ will cause bit $h$ to become $0$ and bit $h-1$ to become $1$, which retain the stated proposition. A similar prove can be done for the right child of $A$. In addition, one also need to prove the termination case to complete this prove, which I also leave out here.