display_bst.js

//Basic string padding functions
function lpad(str, wid) {
	return (" ".repeat(wid) + str).slice(-wid);
}

function rpad(str, wid) {
	return (str + " ".repeat(wid)).slice(0, wid);
}

function cpad(str, wid) {
	var tmp = " ".repeat(wid) + str + " ".repeat(wid);
	var start = Math.floor(tmp.length/2 - wid/2);
	return tmp.slice(start, start + wid);
}

//Render a tree to an array of strings
function render(tree) {
	var cur = "" + tree.key;
	if (!tree.left && !tree.right) return [cur];
	var left = tree.left ? render(tree.left) : [];
	var right = tree.right ? render(tree.right) : [];
	var lwid = left.reduce((w,l) => Math.max(w, l.length), 1) + 1;
	var rwid = right.reduce((w,l) => Math.max(w, l.length), 1) + 1;
	var spare = cur.length - lwid - rwid; //See if we need more room
	if (spare > 0) {
		lwid += Math.ceil(spare / 2);
		rwid += Math.ceil(spare / 2);
	}
	var ret = [cpad(cur, lwid + rwid + 2)];
	for (var i = 0; i < left.length || i < right.length; ++i)
		ret.push(lpad(left[i]||"", lwid) + "  " + rpad(right[i]||"", rwid));
	return ret;
}

//Display a tree on the console.
function display(tree) {
	for (var line of render(tree)) console.log(line + "|");
}

//Construct a tree
function tree(val) {
	return {key: val, left: null, right: null};
}
function add(node, val) {
	while (1) {
		var dir = val < node.key ? "left" : "right";
		if (!node[dir]) return node[dir] = tree(val);
		node = node[dir];
	}
}

function balance(tree) {
	var data = [];
	function walk(tree) {if (tree) {walk(tree.left); data.push(tree.key); walk(tree.right);}}
	walk(tree);
	function build(arr) {
		if (!arr.length) return null;
		return {
			key: arr[Math.floor(arr.length/2)],
			left: build(arr.slice(0, arr.length/2)),
			right: build(arr.slice(arr.length/2 + 1))
		};
	}
	return build(data);
}

//Example usage
var t = tree(12);
for (var n of [15, 10, 66, 25, 22, 4, 90, 50, 35, 70, 31, 18, 44, 24]) add(t, n);

console.log("Original tree:");
display(t);
t = balance(t);
console.log("Balanced tree:");
display(t);