BST basics — search, insert, min/max

Easy

Problem

Implement the core BST operations: search for a value, insert a value while keeping the BST property, and find the minimum and maximum values. Each takes O(h) time, where h is the tree height.

Example 1

Input:  BST [8, 3, 10, 1, 6, null, 14]: search 6, insert 7, min, max
Output: found, 7 becomes the right child of 6, 1, 14

Also asked as: Fina a value in a BST · Find min and max value in a BST

Test cases

Case 1

Input:    [8,3,10,1,6,null,14], 7
Expected: [8,3,10,1,6,null,14,null,null,null,7]

Case 2

Input:    [5], 3
Expected: [5,3]

Case 3

Input:    [5], 9
Expected: [5,null,9]

Case 4

Input:    [], 5
Expected: [5]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Follow the ordering invariant

Time O(h)Space O(1)

Go left if the target is smaller, right if larger. Min is the leftmost node, max the rightmost.

function search(root, key) {
let n = root;
while (n && n.val !== key) n = key < n.val ? n.left : n.right;
return n;
}
function insert(root, key) {
if (!root) return { val: key, left: null, right: null };
if (key < root.val) root.left = insert(root.left, key);
else if (key > root.val) root.right = insert(root.right, key);
return root;
}
const findMin = (n) => { while (n.left) n = n.left; return n.val; };
const findMax = (n) => { while (n.right) n = n.right; return n.val; };