Search code examples
algorithmdata-structuresbinary-treesegment-tree

Why segment tree needs to be a full binary tree?

When constructing a segment tree, why it needs to be a full binary tree? I took some example input arrays and when made them to complete binary tree i am getting the same minimum in a range result. Then why make it a full binary tree when complete binary tree is also giving the same result. Input array- 1, 3, 5, 7, 9, 11

Solution

  • The array representation of the segment tree for example array 1, 3, 5, 7, 9, 11 can be stored like (assuming the range query is finding the minimum element)

    Sorry for a lazy diagram.

    enter image description here

    The number of tree nodes is calculated as pow*2-1 where pow = smallest power of 2 greater than or equal to n.

    Clearly the above segment tree representation is a full binary tree and not a complete binary tree.

    Can you share your segment tree array representation how are you storing it as a complete binary tree?