BST basics — search, insert, min/max
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]
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; };