Write a function to immplement insert in binary search tree

Solution

class BinaryTreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
class Tree:
    def insert(self, root, key):
        if root is None:
            return BinaryTreeNode(key)
        else:
            if root.val == key:
                return root
            elif root.val < key:
                root.right = self.insert(root.right, key)
            else:
                root.left = self.insert(root.left, key)
        return root