BST bug hunt

Questions 1 to 5 of 8

1. 1. This erase_from is part of the lesson's Bst class, but one line is wrong. Node 8 has no left child and has 9 as its right child. What happens to 9 when erase_from removes 8? ``cpp struct Node { int key; std::unique_ptr<Node> left; std::unique_ptr<Node> right; explicit Node(int k) : key(k) {} }; std::unique_ptr<Node> erase_from(std::unique_ptr<Node> node, int key) { if (!node) return nullptr; if (key < node->key) { node->left = erase_from(std::move(node->left), key); return node; } if (key > node->key) { node->right = erase_from(std::move(node->right), key); return node; } if (!node->left) return nullptr; return std::move(node->left); } ``

   9 stays in the tree, because the code moves the right child up9 stays in the tree, because the left-child check returns node 8 unchanged9 is dropped, because the line if (!node->left) return nullptr; returns no subtree9 is dropped, because std::unique_ptr cannot be returned from a function
2. 2. Here is the lesson's contains member, which has one bug. The program inserts 5, then 3, so 3 becomes the left child of 5. contains(3) returns false. Which is the cause? ``cpp bool contains(int key) const { const Node* cur = root_.get(); while (cur != nullptr) { if (key > cur->key) cur = cur->left.get(); else if (key < cur->key) cur = cur->right.get(); else return true; } return false; } ``

   contains compares the key with the root only oncecontains sends a smaller key to the right, but insert_into put it on the leftis_valid rejects the tree, so contains stops earlyinsert never checks for duplicates, so the tree holds two 3s
3. 3. What does this program print? ``cpp #include <iostream> #include <memory> struct Node { int key; std::unique_ptr<Node> left; std::unique_ptr<Node> right; explicit Node(int k) : key(k) {} }; std::unique_ptr<Node> insert(std::unique_ptr<Node> node, int key) { if (!node) return std::make_unique<Node>(key); if (key < node->key) node->left = insert(std::move(node->left), key); else node->right = insert(std::move(node->right), key); return node; } void print(const Node* n) { if (!n) return; print(n->left.get()); std::cout << n->key << ' '; print(n->right.get()); } int main() { std::unique_ptr<Node> root; for (int k : {5, 3, 3, 1}) root = insert(std::move(root), k); print(root.get()); std::cout << "end" << std::endl; } ``

   1 3 5 end5 3 3 1 end3 1 3 5 end1 3 3 5 end
4. 4. After erase(8) in the lesson's second test, the key 9 is lost, yet is_valid() still prints true. Why?

   erase_from keeps every key, so the sorted walk is the sameThe order rule checks that each key sits between its bounds, and a missing key does not break that ruleis_valid checks only the root nodeThe lost node is still in memory, so the rule can see it
5. 5. What does this program print? ``cpp #include <iostream> #include <memory> struct Node { int key; std::unique_ptr<Node> left; std::unique_ptr<Node> right; explicit Node(int k) : key(k) {} }; bool contains(const Node* cur, int key) { while (cur != nullptr) { if (key > cur->key) cur = cur->left.get(); else if (key < cur->key) cur = cur->right.get(); else return true; } return false; } int main() { auto t = std::make_unique<Node>(5); t->left = std::make_unique<Node>(3); t->right = std::make_unique<Node>(8); std::cout << contains(t.get(), 3) << ' ' << contains(t.get(), 8) << ' ' << contains(t.get(), 5) << std::endl; } ``

   1 1 10 1 10 0 11 0 1