Exercise: Is This a Binary Search Tree?

checkLevelOrderBST.js

function checkLevelOrderBST(levelOrder) {
	if (levelOrder.length === 0) return true;
	let i = 0;
	const n = levelOrder.length;
	// Stack to store nodes with their min and max constraints
	const stack = [];
	stack.push({
		data: levelOrder[0],
		min: -Infinity,
		max: Infinity,
	});
	i++;
	while (i < n && stack.length > 0) {
		const { min, max } = stack.pop();
		const current = levelOrder[i];
		// Check if current element violates BST constraints
		if (current <= min || current >= max) {
			return false;
		}
		i++;
		// If there are more elements, check if they can be left or right children
		if (i < n) {
			const next = levelOrder[i];
			// If next element is less than current, it could be left child
			if (next < current) {
				stack.push({
					data: current,
					min: min,
					max: max,
				});
				stack.push({
					data: next,
					min: min,
					max: current,
				});
			} else {
				// Next element is right child of current or belongs to parent
				stack.push({
					data: next,
					min: current,
					max: max,
				});
			}
		}
	}
	return i === n;
}

function processData(input) {
	const lines = input.trim().split("\n");
	const values = lines[1].split(" ").map(Number);
	// Duplicates?
	if (new Set(values).size !== values.length) {
		console.log("No");
		return;
	}
	console.log(checkLevelOrderBST(values) ? "Yes" : "No");
}