Medium Trees
Binary Search Tree
Receives an array of integers and builds a binary search tree: each value is placed by comparison — smaller than a node goes to its left child, larger goes to the right (duplicates are ignored). It then traverses in-order (left subtree, node, right subtree), which always visits the smallest remaining value first. Returns a new array with the values in ascending order.
Visualization
- Input
- Result
Algorithm code
// Binary Search Tree — a single pure function. Builds a BST from the given
// values (duplicates ignored) and returns them via in-order traversal, i.e.
// ascending order. Internal helpers keep insertion and traversal readable.
/**
* @param {number[]} values - values to insert, in order
* @returns {number[]} the values in ascending (in-order) order
*/
export function binarySearchTreeInorder(values) {
const insert = (node, value) => {
if (node === null) {
return { value, left: null, right: null };
}
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
}
return node;
};
let root = null;
for (const value of values) {
root = insert(root, value);
}
const out = [];
const walk = (node) => {
if (node === null) {
return;
}
walk(node.left);
out.push(node.value);
walk(node.right);
};
walk(root);
return out;
}FUNCTION binarySearchTreeInorder(values):
root ← null
// Build the BST — duplicates are ignored
FOR EACH value IN values:
root ← insert(root, value)
// Collect nodes via in-order traversal (left → root → right)
out ← []
walk(root, out)
RETURN out
FUNCTION insert(node, value):
IF node = null:
RETURN Node(value, left: null, right: null)
IF value < node.value:
node.left ← insert(node.left, value)
ELSE IF value > node.value:
node.right ← insert(node.right, value)
RETURN node
FUNCTION walk(node, out):
IF node = null: RETURN
walk(node.left, out)
APPEND node.value TO out
walk(node.right, out)