Everything in the left subtree is smaller than node. Everything in the right subtree is greater than node. [left subtree] < x < [right subtree]
The idea is used to end up on the correct node. Just looking at these three problems is enough
Search
TreeNode* searchBST(TreeNode* root, int val) {
while (root) {
if (root->val == val) {
return root;
}
if (val < root->val) {
root = root->left;
} else {
root = root->right;
}
}
return nullptr;
}Insert
Due to how cpp lose “linkage” to parent if you end up on a null, the iterative way either needs a parent that I keep track of I don’t recurse into null nodes at all.
Iterative
TreeNode* insertIntoBST(TreeNode* root, int val) {
auto old_root = root;
auto node = new TreeNode(val);
if(!root) return node;
while (root) {
if (val < root->val) {
if (root->left == nullptr) {
root->left = node;
break;
}
root = root->left;
} else {
if (root->right == nullptr) {
root->right = node;
break;
}
root = root->right;
}
}
return old_root;
}Recursive here ( or rather in cpp ) makes it very clean though. Because you “return” roots, you can just “assing” it at the parent’s level
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root)
return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}LCA
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// an lca would be SO positioned that
// p < lca and q > lca as entire subtrees change for the lowest common
// one otherwise it's just not the lowest common what if one is ancestor
// of other? I mean we'll still naturally fall onto that node
TreeNode* par;
int mx = max(p->val, q->val);
int mn = min(p->val, q->val);
while (root) {
par = root;
if (mx < root->val)
root = root->left;
else if (mn > root->val)
root = root->right;
else
break;
}
return par;
}Delete node **
If there’s just one child it’s trivial, think of the two child case.
Say x is to be deleted and we still want to preserve this invariant. [left subtree] < x < [right subtree] Naturally, you replace x with the max of the left subtree ( rightmost ) or the min of the right subtree ( leftmost )
The implementation can be tricky depending on how you go about it, C++ will have that same par keeping problem.
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root)
return nullptr;
if (key < root->val)
// notice this assignment
root -> left = deleteNode(root->left, key);
else if (key > root->val)
root->right = deleteNode(root->right, key);
else {
if (!root->left)
return root->right;
if (!root->right)
return root->left;
// min in right
TreeNode* nxt = root->right;
while(nxt->left) nxt = nxt->left;
// overwrite val
root->val = nxt->val;
// del nxt from right
root->right = deleteNode(root->right, nxt->val);
}
return root;
}Trim Tree **
Similar to delete, the impl can go ugly if you let it.
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (!root)
return nullptr;
// for root, return the new trimmed root
if (root->val < low) // all of root -> left is gone
return trimBST(root->right, low, high);
if (root->val > high)
return trimBST(root->left, low, high);
// root is to be kept so only prune children
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}