binarysearch.js

"use strict"
//node --harmony binarysearch.js


// Input: sorted array
// Output: binary search tree
//
// wtf is a binary search tree?
// let me explain lols.
//
// 1 2 3 4 5 6 7
// let's build a binary search tree.
// it's a search tree.
// prolly balanced. am i right?
//
//     4
//  2     6
// 1 3   5 7
//
// I think that's right...
//
// So, sorted array is a good representation of a binary search tree.
//
// First, let's try to print a sorted array in the form of binary search tree.
// Hoa, in the form. That so elegant. I like classy ladies.
//
function printSortedArrayAsBinarySearchTree(sortedArr) {
    // so you have an array.
    // you print the middle number with indentation lols.
    // then you recurse to print left part and right part with indentation.
    // let's say input is 1 2 3 4 5 6 7
    // begin index is 0
    // end index is 7, 1+ last index.
    // middle index is 3, (7 - 0) / 2.
    // so, you print arr[3] with indentation.
    // indentation is numOfDigit(arr[6]) * 3.
    // 
    // then you print the left and right, the next level.
    // let's recurse.
    // begin index is 0.
    // end index is 3.
    // middle index is 1.
    // so you print arr[1], 2, with indentation.
    // indentation is numOfDigit(arr[arr.length]) * 1.
    //
    // for right,
    // begin index is 4.
    // end index is 7.
    // middle index is 5, 4 + (7 - 4) / 2
    // so, you print arr[5], 6, with indentation.
    // left part already printed indentation.
    // right part's indentation is  
    //  numOfDigit(arr[arr.length]) * 5 - left part's indentation.
    // i think that's right.
    //
    // so, when do you stop recursion?
    // let's recurse once more.
    // left part:
    // begin index: 0
    // end index is: 1
    // middle index is: 0.
    // print: arr[0], 1.
    // indentation: 0
    //
    // right part:
    // begin index: 2
    // end index: 3
    // middle index: 2.
    // print: arr[2], 3.
    // indentation: 0 + n*2.
    //
    // recurse once more:
    // left part:
    // begin index: 0
    // end index: 0.
    // stop because begin index == end index.
    //
    // right part:
    // begin index: 2
    // end index: 1
    // stop because begin index >= end index.
    //
    //

    const n = sortedArr.length;
    const maxNumOfDigits = sortedArr[n-1].toString().length;
    const indentWidth = maxNumOfDigits + 1; //space.
    let prevIndentation = 0;
    const queue = [buildSpec(0, n)];

    while (queue.length > 0) {
        const spec = queue.shift();
        const begin = spec.begin;
        const end = spec.end;
        if (begin >= end) {
            continue;
        }
        const middle = getMiddle(begin, end);
        const indentation = getIndentation(middle) - prevIndentation;
        const indentStr = Array(indentation + 1).join(' ');
        const output = indentStr+sortedArr[middle];
        process.stdout.write(output);
        prevIndentation += output.length;
        
        const isRightMost = end === n; 
        if (isRightMost) {
            process.stdout.write('\n');
            prevIndentation = 0;
        }
        
        queue.push(buildSpec(begin, middle));
        queue.push(buildSpec(middle+1, end));
    }
    process.stdout.write('\n');

    function buildSpec(begin, end) {
        return {begin: begin, end: end}
    }

    function getMiddle(begin, end) {
        return begin + Math.floor((end - begin)/2);
    }

    function getIndentation(middle) {
        return indentWidth * middle;
    }

}

const input = process.argv.slice(2).map(function(x) { return parseInt(x,10); });
if (input.length <= 0) {
    throw Error("need sorted array of integers. For example, 1 2 3 4 5");
}
console.dir(input);
printSortedArrayAsBinarySearchTree(input);