2-3 tree implementation from sorted array in O(n)-time

[Saeven]

Hello,

I've a quick question - anyone have an idea on what an efficient manner of building a 2-3 tree from a sorted array A[1..n] in O(n) time could be?

Thanks!
Alexandre

[Yves M]

I guess you could just build a perfectly balanced binary tree and then pretend that it's a 2-3 tree (it would be an all 2 tree).

The algorithm could easily be done in a divide and conquer style with recursion. Split the array in 2 and call recursively until you arrive at an interval which contains 1 or 0 entries. if it's 1, generate a new leaf, otherwise pass back null. Then at the recursion level above, combine the outputs of the two previous ones into an internal node. Running time would be O(N) and recursion depth would be log(N). I guess you can easily convert this to an iterative solution as well.

Yves