Easy difficulty · Algorithm · Topics: tree, bst, searching
Searching a binary search tree uses the ordering of the tree to throw away half of the remaining values at each step. This sample builds a BST from the given insertion order, then searches for target iteratively and returns the path of values it visited. If the path ends with the target it was found; otherwise the search fell off the tree.
At each node there are three outcomes: the target equals the node's value (done), it is smaller (everything larger is in the right subtree, so ignore it) or it is larger (ignore the left subtree). It is binary search, except that the "middle" is the current node and the array is replaced by pointers.
Invariant: if the target exists in the tree, it is in the subtree rooted at curr. Each step keeps that true while shrinking the subtree, so the walk either reaches the target or ends at a null child that proves it is absent.
curr = root with an empty path.curr is not null:
curr.val to path.target === curr.valpathtarget < curr.val, move to curr.left; otherwise move to curr.right.curr is null, the value is not in the tree: return the path anyway (its last value is where the target would be inserted below).Test case 0 builds the BST from [8, 3, 10, 1, 6, 14, 4, 7, 13] and searches for 6:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
| Step | curr | Compare | Move | path |
|---|---|---|---|---|
| 1 | 8 | 6 < 8 | left | [8] |
| 2 | 3 | 6 > 3 | right | [8, 3] |
| 3 | 6 | 6 === 6 | found, return | [8, 3, 6] |
Other cases: searching for 5 returns [8, 3, 6, 4] (it falls off the tree below 4, so 5 is absent); searching for 13 returns [8, 10, 14, 13].
| Measure | Cost | Why |
|---|---|---|
| Time, average | O(log n) | Each step discards a whole subtree of a balanced tree |
| Time, worst | O(n) | A degenerate (chain-like) tree has height n |
| Space | O(1) | Iterative: one pointer (plus the path output) |
curr.val when curr is null; the loop condition must test it first.curr pointer descending one level per iteration, always away from the discarded side.path growing by one value per step, matching the highlighted route from the root.return when found, or curr becoming null.Input: values = [8, 3, 10, 1, 6, 14, 4, 7, 13], target = 6
Output: [8, 3, 6]
// Returns the values visited while searching for `target`.
// If the last value in the path equals `target`, it was found.
function bstSearch(values, target) {
const root = buildBst(values);
const path = [];
let curr = root;
while (curr !== null) {
path.push(curr.val);
if (target === curr.val) {
return path; // found
}
// Discard the half that cannot contain the target.
if (target < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
return path; // fell off the tree: not present
}
function buildBst(values) {
let root = null;
for (const value of values) {
const node = new TreeNode(value);
if (root === null) {
root = node;
continue;
}
let curr = root;
while (true) {
if (value < curr.val) {
if (curr.left === null) {
curr.left = node;
break;
}
curr = curr.left;
} else {
if (curr.right === null) {
curr.right = node;
break;
}
curr = curr.right;
}
}
}
return root;
}