Lessons · TypeScript · binary trees
A node, a left and a right
A binary tree node holds a value and at most two children. In a binary SEARCH tree everything left is smaller and everything right is larger.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
That one rule lets a search discard half the remaining tree at every step, which is why sorted maps and database indexes are shaped like this.
How to think about it
Three lines of thought for almost any tree function: the answer for an empty tree, the answer for this node, and what you ask of the two children. Write those and the recursion falls out.
Worked example
const node = (value, left = null, right = null) => ({ value, left, right });const root = node(5, node(3, node(1), node(4)), node(8));Left of 5 is smaller; right is larger.
function find(n, wanted) {if (n === null) return false;Empty: not here.
if (n.value === wanted) return true;This node.
return wanted < n.value ? find(n.left, wanted) : find(n.right, wanted);One side is discarded whole.
}
console.log(find(root, 4), find(root, 7));true false
const height = n => (n === null ? 0 : 1 + Math.max(height(n.left), height(n.right)));The three lines again.
console.log(height(root));3
Your turn
Take the branch that can still hold the value.
if (wanted < n.value) return find(n., wanted);
Solve one with the tests running
The trap
The speed depends on balance. Insert 1, 2, 3, 4, 5 in order and every node has only a right child: a linked list in a tree's clothes, and every search is back to n steps.