Question

Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None:...

Create an add method for the BST (Binary Search Tree) class.

"""This method adds new value to the tree, maintaining BST property. Duplicates must be allowed and placed in the right subtree."""

Example #1: tree = BST()

print(tree)

print(tree)

print(tree)

Output:

TREE in order { }

TREE in order { 5, 10, 15 }

TREE in order { 5, 10, 15, 15, 15 }

TREE in order { 5, 5, 10, 15, 15, 15 }

Code:

```class Stack:
"""
Supported methods are: push, pop, top, is_empty

DO NOT CHANGE THIS CLASS IN ANY WAY
YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION
"""
def __init__(self):
""" Initialize empty stack based on Python list """
self._data = []

def push(self, value: object) -> None:
""" Add new element on top of the stack """
self._data.append(value)

def pop(self) -> object:
""" Remove element from top of the stack and return its value """
return self._data.pop()

def top(self) -> object:
""" Return value of top element without removing from stack """
return self._data[-1]

def is_empty(self):
""" Return True if the stack is empty, return False otherwise """
return len(self._data) == 0

def __str__(self):
""" Return content of the stack as a string (for use with print) """
data_str = [str(i) for i in self._data]
return "STACK: { " + ", ".join(data_str) + " }"

class Queue:
"""
Supported methods are: enqueue, dequeue, is_empty

DO NOT CHANGE THIS CLASS IN ANY WAY
YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION
"""
def __init__(self):
""" Initialize empty queue based on Python list """
self._data = []

def enqueue(self, value: object) -> None:
""" Add new element to the end of the queue """
self._data.append(value)

def dequeue(self) -> object:
""" Remove element from the beginning of the queue and return its value """
return self._data.pop(0)

def is_empty(self):
""" Return True if the queue is empty, return False otherwise """
return len(self._data) == 0

def __str__(self):
""" Return content of the stack as a string (for use with print) """
data_str = [str(i) for i in self._data]
return "QUEUE { " + ", ".join(data_str) + " }"

class TreeNode:
"""
Binary Search Tree Node class
DO NOT CHANGE THIS CLASS IN ANY WAY
"""
def __init__(self, value: object) -> None:
"""
Init new Binary Search Tree
DO NOT CHANGE THIS METHOD IN ANY WAY
"""
self.value = value          # to store node's data
self.left = None            # pointer to root of left subtree
self.right = None           # pointer to root of right subtree

def __str__(self):
return str(self.value)

class BST:
def __init__(self, start_tree=None) -> None:
"""
Init new Binary Search Tree
DO NOT CHANGE THIS METHOD IN ANY WAY
"""
self.root = None

# populate BST with initial values (if provided)
# before using this feature, implement add() method
if start_tree is not None:
for value in start_tree:

def __str__(self) -> str:
"""
Return content of BST in human-readable form using in-order traversal
DO NOT CHANGE THIS METHOD IN ANY WAY
"""
values = []
self._str_helper(self.root, values)
return "TREE in order { " + ", ".join(values) + " }"

def _str_helper(self, cur, values):
"""
Helper method for __str__. Does in-order tree traversal
DO NOT CHANGE THIS METHOD IN ANY WAY
"""
# base case
if cur is None:
return
# recursive case for left subtree
if cur.left:
self._str_helper(cur.left, values)
# store value of current node
values.append(str(cur.value))
# recursive case for right subtree
if cur.right:
self._str_helper(cur.right, values)

def add(self, value: object) -> None:```

If you have any doubts, please ask in the comments, I will try to solve it as soon as possible. If you find my answer helpful, do UPVOTE.Thanks

The required add function is given below:

def add(self, value: object) -> None:
#new node to be inserted
node = TreeNode(value)

#pointer to store the place
#where the new element has to inserted
x = self.root

# Pointer y maintains the the last position
# of pointer x
y = None

while (x != None):
y = x
if (value < x.value):
x = x.left
else:
x = x.right

# If the tree is empty,
#i.e y=None. Then we assign node as the root
if (y == None):
y = node
self.root=y

# If the new value is smaller/lesser then the leaf node value
# We make the new node its left child
elif (value < y.value):
y.left = node

# else make the new node its
# right child
else:
y.right = node

Code Snippet:

Please refer to the given code snippet for the identation.

Output:

I have tested the add function with the code given, the output for the same is given below. It matches the output exactly as the output given in question.