Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$?
For example why are the children of node 3 six and seven? Is there a mathematical way to prove this? Thanks
This is only true because it is a complete binary tree.
There are twice as many nodes in each succeeding level (starting from the root at level $k=0$). Thus, at level $k$, there are $2^k$ nodes and the index of the first node is $2^0 + 2^1 + \dots + 2^{k-1} + 1 = 2^k$.
At level $k$, the children of the first node (index $N = 2^k$) will be labeled as soon as the remaining $2^k-1$ nodes on level $k$ have been labeled. Thus the first child will have index $$2^k + (2^k - 1) + 1 = 2 \cdot 2^k = 2N$$ and the next child will have $2N+1$.
The parent node of index $N+1$ will have the children with succeeding child indices, i.e. $2N+2 = 2(N+1)$ and $2N+3 = 2(N+1)+1$ thus the pattern is preserved. This holds for any level $k$.
When talking about indexing, it provides a structured way of accessing the array elements. It's not so much a mathematical property of a binary tree (at least, that's not how I'd look at it), as more of a way of modeling the data for efficient lookup and storage in an array.
An array based solution allows for a compact representation of the tree. You commonly see this in a binary heap data structure. One nice aspect is that when percolating an element upwards after the root has been removed, we can simply swap array elements rather than worrying about updating node pointers.
In reality, you can adopt whatever indexing convention you want. This one happens to make sense though.
Also, this property holds for all k-regular trees. So for a ternary tree, we index using 3n, 3n+1, and 3n+2. Notice the quotient-remainder theorem coming into play here. Since a binary tree is a 2-regular tree (obviously excluding leaves), the $2$ ensures that a node's children appear after its siblings. So on level $1$ with nodes $n_{2}, n_{3}$, $n_{2}$'s children are $n_{4}$, $n_{5}$, which puts them past $n_{3}$ without wasting empty array spots. As we add $2k$ nodes to level $k$, we need to make sure we allocate double the space for the first node's children at that level. Naslundx did a good job of showing this formally. Hopefully this adds some intuition as to why we choose this indexing schema, as well as why it works.
Count all the nodes up to and including the second (highest numbered) child of node $n$; the number of such nodes is the number attached to this second child. But each node so counted is either the root node, or one of the two children of a parent node whose number is in the range $1,\ldots,n$. Conversely for any such parent both children are among the counted nodes. So the number of nodes counted is $2n+1$, and the children of node $n$ are numbers $2n$ and $2n+1$.
