[voraa]

ту тут уж придётся бинароное дерево городить вместо массива

Зачем дерево?
Бинарный поиск по отсортированному массиву.

Как то так

// ищет в отсортированном массиве arr 
// индекс первого элемента >= val 
// выдает arr.length, если все элементы < val
const findBinIndex =(arr, val) => {
	let nb=0, ne=arr.length-1;
	if (val<=arr[0]) return 0;
	if (val >= arr[ne]) return ne+1;
	let index;
	while (true) {
		index = ((ne + nb) / 2) | 0;
		if (arr[index] <= val)
			nb = index;
		else 
			ne = index;
			
		if (ne - nb == 1) {
			if (val<=arr[nb]) return nb;
			if (val >= arr[ne]) return ne+1;
			return ne;
		}
	}
}

const arr =  ['ABC', 'BCD','BCD', 'CAE', 'CBA']
let k, el;
el = 'BAS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'AAS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'CCS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'BCD';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'CAF';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

console.log(arr)