COPY PASTABLE CODE: Python 3 Binary Search Trees

BST is a binary tree where nodes are ordered in the following way:

each node contains one key (also known as data)

the keys in the left subtree are less then the key in its parent node, in short L

the keys in the right subtree are greater the key in its parent node, in short P

duplicate keys are not allowed.

In the following tree all nodes in the left subtree of 8 have keys 8. Because both the left and right subtrees of a BST are again search trees; the above definition is recursively applied to all internal nodes PROBLEM:

Find min element in the binary tree.

Write a function that finds the smallest element in the binary tree: def tree_min(self): ### your code here return

PROBLEM: Are you a binary search tree?

For example (a) is a not BST (why?) whereas (b) is a proper BST.

Using functions that allow you to find min and max elements, implement a recursive function isBst(self, tr), which takes an instance of the BinaryTree class and returns True if it is a valid BST.

Note: an empty BinaryTree is a valid binary search tree. This function should be a part of the BinaryTree class. def isBst (self):

''' >>> t = BinaryTree(1, BinaryTree(1), BinaryTree(2))

>>> t.isBst()

False '''

### your code here return

Expected outputs:

Hint: use the definition of a BST and apply recursion to left and right subtrees of tr.

8 3 10 1 6 14 4 7 (13