SearchTree.js

//Utility function to display a binary tree to the console
//More helpful than console.log(tree) due to circular parent refs
//Usage: print_tree(some_tree)
function print_tree(tree, depth) {
	if (!depth) {
		console.log("" + tree.key);
		depth = 0;
	}
	depth += 1;
	if (tree.left) {
		console.log(" ".repeat(depth) + "<" + tree.left.key);
		print_tree(tree.left, depth);
	}
	if (tree.right) {
		console.log(" ".repeat(depth) + ">" + tree.right.key);
		print_tree(tree.right, depth);
	}
}

//Write an algorithm to check whether an arbitrary tree is a binary search tree
function is_bst(tree) {
	//This is a bit sloppy; a non-binary tree won't have "left" and "right"
	//attributes, yet we attempt to prove that it is indeed binary. Whatever.
	//Also, this will only notice if the immediate child is out of order. It
	//is possible for a flawed tree to pass this test.
	if (tree.children > 2) return false;
	if (tree.left) {
		if (tree.left.key > tree.key) return false;
		if (!is_bst(tree.left)) return false;
	}
	if (tree.right) {
		if (tree.right.key < tree.key) return false;
		if (!is_bst(tree.right)) return false;
	}
	return true;
}

//More strict version of the above: a tree must have all its keys within bounds
//(either bound may be 'undefined' if there is no such bound).
//Assumes you're working with a binary tree, because let's face it, it makes
//no sense to ask if an integer is a BST.
function is_bst(tree, minimum, maximum) {
	if (minimum !== undefined && tree.key < minimum) return false;
	if (maximum !== undefined && tree.key > maximum) return false;
	if (tree.left  && !is_bst(tree.left , minimum, tree.key)) return false;
	if (tree.right && !is_bst(tree.right, tree.key, maximum)) return false;
	return true;
}

//Write an algorithm to find the height of a binary search tree
function bst_height(tree) {
	return Math.max(tree.left && bst_height(tree.left),
		tree.right && bst_height(tree.right)) + 1;
}

//Write an algorithm to find the third largest value in a binary search tree
//CJA 20160822: Assuming that this means the third largest *key*.

function nth_largest(tree, state) {
	//Finding the largest node means traversing the right first.
	//Normally, you'll traverse a tree left-to-right.
	if (tree.right) {
		nth_largest(tree.right, state);
		if (state.result) return;
	}
	if (!--state.n) {
		//Found it.
		state.result = tree.key;
		return;
	}
	if (tree.left) nth_largest(tree.left, state);
}

function third_largest(tree) {
	//Special case: empty tree.
	if (tree.key == null) return null;
	var state = {n: 3, result: null};
	nth_largest(tree, state);
	return state.result;
}