Binary Search Tree Mods

The binary search tree program that we've got at this point doesn't behave quite correctly. Recall that we should be able to place key-value pairs into the binary tree, and if we enter a new value with the same key, the new value should replace the old value for that key.

Our current binary search tree, when we try to call put(key, value), actually adds a duplicate key. We can demonstrate this by:

1. Modifying the line

    yield self.key

   so that it says

    yield self.key, self.payload

   This has the effect of displaying both the key and its value when we iterate through the tree.

2. Run this main program and observe what is displayed:

    def main():
        print("Testing BinarySearchTree class")
        bst = BinarySearchTree()
        bst.put(2,"Hi")
        bst.put(1,"Hello")
        bst.put(3,"What's up?")
        for el in bst:
            print(el)
   
        print("Trying to replace key 1...")
        bst.put(1,"Hey!")
        for el in bst:
            print(el)    

   You'll see this output

    Testing BinarySearchTree class
    (1, 'Hello')
    (2, 'Hi')
    (3, "What's up?")
    Trying to replace key 1...
    (1, 'Hello')
    (1, 'Hey!')
    (2, 'Hi')
    (3, "What's up?")

Modify your binary search tree program so that it behaves as it should: if an instruction uses put(key, value) to put a key into the tree that is already there, it just replaces the value of the current key.