Building segment tree without adding extra elements to its size

I recently learned about segment trees as data structures, and what I learned was that we are always building segment tree with size $N$ such that $N$ is power of two. If $N$ is not power of two we can add more elements to the end of the tree.

However, I was wondering is the segment tree going to work normally if we don't add more elements to make its size power of two.

Example

If the size of segment tree is 8, then we have array of size 15, $15 = 2 \cdot 8-1$
In this array we keep track of the intervals, where we have the interval $[1,8]$ on index 1, and on index $2\cdot 1$ we keep the left child, and the right child is on index $2\cdot1+1$.

So our array looks like following:

index $1: [1, 8], 2: [1, 4], 3: [5, 8], 4: [1,2], 5:[3, 4],6:[5, 6], 7:[7, 8]$, $8[1, 1], 9:[2, 2], 10:[3,3], 11:[4,4], 12:[5,5], 13:[6,6], 14:[7, 7], 15:[8,8]$

Now my question is this: If we run this algorithm for dividing and building the segment tree for numbers that are not power of two (ex. 7, 11, 15).. is it going to build the segment tree normaly, because the segment tree is not going to be full balanced then.

A segment tree is not required to be full (which is what I believe you mean), however it will always be complete. That is, every level, except possibly the last, is filled.

Take a look at the structure and construction to see that it says nowhere that was must have $2^k - 1$ nodes in the tree. For example we may have $2^{k-1}

• Our tree if we do not fill up the last layer and left leaves as is.

Clearly (1) should look more appealing, but it is also functionally more appealing. There is only one leaf level, so we need no conditional checking if we are at a leaf or not, we just check which iteration into the tree we are at. There are simply more checks to do per iteration and it is not worth it over filling in the final level. So you can do it, but I wouldn't.

StackExchange Computer Science Q#79860, answer score: 7