Problem Statement: Given a list of integers arrange them in ascending order
Solution: We first create a binary search for the input values and then we do the in-Order traversal of that tree which results in a sorted list of integers.
Binary Search Tree Sort125 views
function binarySearchTreeSort(list){
function inOrderTraversal(node){
var ret = [];
if(node){
ret = ret.concat(inOrderTraversal(node.left));
ret.push(node.val);
ret = ret.concat(inOrderTraversal(node.right));
}
return ret;
}
var i,node,cur,root={val:list[0]},child;
for(i=1;i<list.length;i++){
node = {val:list[i]};
cur = root;
while(cur!=node){
child = node.val<cur.val?'left':'right';
cur[child]= cur[child]?cur[child]:node;
cur = cur[child];
}
}
return inOrderTraversal(root);
}