Every BST operation starts the same way: stand at the root, compare, and go left if the value is smaller or right if it's bigger. Searching stops when it finds the value; inserting keeps going until it falls off the tree, and puts the new node in that empty spot. Both can be written recursively or with a loop — this lesson shows both, plus the two easiest searches of all, the minimum and the maximum.
Compare the target with the node. Equal: found. Smaller: it can only be in the left subtree. Bigger: only in the right. If you reach an empty child, the value isn't in the tree. The recursive version reads like the definition; the loop does the same walk with no call stack, so it uses O(1) memory.
Each comparison throws away a whole side of the tree.
function search(node, target) { if (node === null || node.val === target) return node; // not there, or found return target < node.val ? search(node.left, target) : search(node.right, target);}function search(root, target) { let node = root; while (node !== null) { if (target === node.val) return node; // found it if (target < node.val) { node = node.left; // everything on the right is bigger: skip it } else { node = node.right; // everything on the left is smaller: skip it } } return null; // fell off the tree: not there}Time O(h) either way. Space O(h) for the recursion's call stack, O(1) for the loop.
The smallest value is as far left as you can go: every step left reaches something smaller, and a node with no left child has nothing smaller below it. The largest is as far right as you can go. No comparisons needed at all.
function findMin(root) { let node = root; while (node.left !== null) node = node.left; // smaller values are always to the left return node.val;} function findMax(root) { let node = root; while (node.right !== null) node = node.right; // bigger values are always to the right return node.val;}Time O(h), space O(1). In the tree above: the minimum is 1 (8 → 3 → 1) and the maximum is 14 (8 → 10 → 14).
Inserting is a search for a value that isn't there: follow the comparisons until the next step would leave the tree, and hang the new node on that empty side. The new node is always a leaf, and nothing else in the tree moves. The recursive version returns each subtree's (possibly new) root and re-attaches it on the way back up; the loop remembers the parent so it can attach the new node to it.
The new value follows the comparisons down and becomes a leaf where the path runs out.
function insert(node, val) { if (node === null) return new TreeNode(val); // fell off the tree: the new node goes here if (val < node.val) node.left = insert(node.left, val); else node.right = insert(node.right, val); return node;}function insert(root, val) { const fresh = new TreeNode(val); if (root === null) return fresh; // an empty tree: the new node is the root let node = root; while (true) { if (val < node.val) { if (node.left === null) { node.left = fresh; break; } // empty spot on the left node = node.left; } else { if (node.right === null) { node.right = fresh; break; } // empty spot on the right node = node.right; } } return root;}Time O(h); space O(h) recursive, O(1) with the loop.
