Easy Trees
In-order Traversal
Receives an array of integers and interprets it as a binary tree laid out level-order — index i's children live at 2i+1 and 2i+2, the same indexing scheme used by binary heaps. It then walks the tree recursively in-order: fully visit the left subtree, process the current node, then fully visit the right subtree. Returns a new array with the values in the order they were visited. Unlike a binary search tree, this tree has no ordering property, so the result is not necessarily sorted — it reflects the tree's shape, not the values themselves.
Visualization
- Input
- Result
Algorithm code
// In-order Traversal — a single pure function. Interprets the given values
// as a complete binary tree laid out level-order (index i's children live
// at 2i+1 and 2i+2), then walks it recursively in-order (left, node, right).
/**
* @param {number[]} values - tree nodes in level-order (index i's children are at 2i+1 and 2i+2)
* @returns {number[]} the values in in-order (left, node, right) order
*/
export function inorderTraversal(values) {
const out = [];
const walk = (index) => {
if (index >= values.length) {
return;
}
walk(2 * index + 1);
out.push(values[index]);
walk(2 * index + 2);
};
walk(0);
return out;
}FUNCTION inorderTraversal(values):
out ← []
walk(0, values, out)
RETURN out
FUNCTION walk(index, values, out):
IF index >= LENGTH(values): RETURN
walk(2 * index + 1, values, out)
APPEND values[index] TO out
walk(2 * index + 2, values, out)