Why segment tree has to be a binary tree only, why can’t it be ternary, or say n-ary tree, where n >2?

Question

In segment trees , we divide the array into 2 halves and carry it on recursively. Why can’t they be divided into,,let’s day , 3 halves, representing 3 segments. Why is it a binary tree?

Answer 1

Well, You can ask the same question about binary search or any binary decision based data structure like a binary search tree. There are two main reasons for this.

1. The implementation becomes ugly, with multiple if else conditions.
2. It doesn't actually improve the asymptotic time complexity (time complexity is still O(logn))

You might think that breaking an array into 3 parts instead of 2 might get you a speed up, but this not true. Since if you break an array into 3 parts each one third of the original size, then you might in the worst case recurse on 2/3rds size of the orignal array always, there by making the running time worst than binary search.