BST bug hunt

Questions 1 to 5 of 8

1. 1. Calling this insert method with 5, and then with 5 again, makes inorder() print [5, 5] and size 2. Why? ``python def insert(self, key): self.size += 1 if self.root is None: self.root = Node(key) return cur = self.root while True: if key < cur.key: if cur.left is None: cur.left = Node(key) return cur = cur.left else: if cur.right is None: cur.right = Node(key) return cur = cur.right ``

   The comparison key < cur.key is wrong for ints, so 5 always goes to the leftThe root is never set, so the second 5 is stored in a separate treeThe method never checks for an equal key, so every call stores a new node and counts itself.size += 1 runs only when the tree is empty, so size is counted twice
2. 2. A search for 1000 returns False, even though 1000 was inserted with key = int('1000'). This is the loop in contains. ``python cur = self.root while cur is not None: if cur.key is key: return True cur = cur.left if key < cur.key else cur.right return False `` Which change fixes it?

   Use key == cur.key, which compares the numbers instead of the objectsChange the first if to cur.key <= keyMove the return True after the loopStore the keys as str so that is compares the text
3. 3. Deleting 70 from a tree where 70 has only a right child (80) drops 80 from the walk, and the size still goes down by one. Which line causes this? ``python if n.left is None or n.right is None: return n.left ``

   if key < n.key, which sends the key to the wrong sidewhile succ.left is not None, which walks too far downif n.left is None or n.right is None, which tests the wrong childrenreturn n.left, which returns None when the only child is on the right
4. 4. Deleting 40 from a tree whose root has two children leaves 50 in the walk twice. Which part is the bug? ``python succ = n.right while succ.left is not None: succ = succ.left n.key = succ.key return n ``

   The loop searches for the successor in the left subtreeAfter copying the successor's key into n, the method never removes the successor from the right subtreeThe method returns n.left when both children existThe method runs self.size -= 1 once for the copy
5. 5. What does this program print? ``python a = int('100') b = int('100') c = int('1000') d = int('1000') print(a is b, c is d, c == d) ``

   True True TrueTrue False TrueFalse False TrueTrue False False