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.

add(self, new_value: object) -> None:

"""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) tree.add(10)

tree.add(15)

tree.add(5)

print(tree)

tree.add(15)

tree.add(15)

print(tree)

tree.add(5)

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:
    """
    Class implementing STACK ADT.
    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:
    """
    Class implementing QUEUE ADT.
    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:
                self.add(value)

    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:

Homework Answers

Answer #1

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.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
"""linkedQueue.py implements LinkedQueue""" class Node(object): def __init__(self, e, nextNode): self.item, self.next = (e, nextNode) def __str__(self):...
"""linkedQueue.py implements LinkedQueue""" class Node(object): def __init__(self, e, nextNode): self.item, self.next = (e, nextNode) def __str__(self): return str(self.item)    class LinkedQueue(object): def __init__(self): #O(1) self._front, self._rear =(None, None) self._size = 0    def enqueue(self, e): # add e to the rear of the queue. newTail = Node(e, None) if self.isEmpty(): self._front = newTail else: self._rear.next = newTail self._rear = newTail self._size += 1 def front(self): # raise exception if it is empty, otherwise return front element if self.isEmpty(): raise Exception("call...
Please answer the following as soon as possible. Thank you. Add the top method in class...
Please answer the following as soon as possible. Thank you. Add the top method in class Stack to the following python code which returns the top item of the stack. Test it. Design top() method using a single queue as an instance variable, and only constant additional local memory within the method bodies. python code: class Stack: def __init__(self): self.q = Queue() def is_empty(self): return self.q.is_empty() def push(self, data): self.q.enqueue(data) def pop(self): for _ in range(self.q.get_size() - 1): dequeued =...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Given the list of values below, create a Binary Search Tree for the list, Use the...
Given the list of values below, create a Binary Search Tree for the list, Use the first value in the list as the root of the tree, add the nodes to BST in the order they appear in the list.[50, 44, 82, 39, 35, 98, 87, 100, 74, 23, 34, 14, 94] What is the minimum height of a Binary Tree that contains 24nodes? What is the minimum height of a Binary Tree that contains 64nodes? What is the minimum...
Python Blackjack Game Here are some special cases to consider. If the Dealer goes over 21,...
Python Blackjack Game Here are some special cases to consider. If the Dealer goes over 21, all players who are still standing win. But the players that are not standing have already lost. If the Dealer does not go over 21 but stands on say 19 points then all players having points greater than 19 win. All players having points less than 19 lose. All players having points equal to 19 tie. The program should stop asking to hit if...
Assignment Statement Use the skeleton file starter code (below) to create the following classes using inheritance:...
Assignment Statement Use the skeleton file starter code (below) to create the following classes using inheritance: ⦁   A base class called Pet ⦁   A mix-in class called Jumper ⦁   A Dog class and a Cat class that each inherit from Pet and jumper ⦁   Two classes that inherit from Dog: BigDog and SmallDog ⦁   One classes that inherit from Cat: HouseCat The general skeleton of the Pet, Dog, and BigDog classes will be given to you (see below, "Skeleton", but...
Program will allow anywhere between 1 and 6 players (inclusive). Here is what your output will...
Program will allow anywhere between 1 and 6 players (inclusive). Here is what your output will look like: Enter number of players: 2 Player 1: 7S 5D - 12 points Player 2: 4H JC - 14 points Dealer: 10D Player 1, do you want to hit? [y / n]: y Player 1: 7S 5D 8H - 20 points Player 1, do you want to hit? [y / n]: n Player 2, do you want to hit? [y / n]: y...
I need some tests for this python class. some tests for some of the functions in...
I need some tests for this python class. some tests for some of the functions in this class like. def __init__ def __eq__ def __lt__ def __hash__ I am using Pycharm and useing Pytest to write some tests but have no idea how to write one --------------------------------------------------------------------------------------------------- class Movie: def __set_title_internal(self, title: str): if title.strip() == "" or type(title) is not str: self.__title = None else: self.__title = title.strip() def __set_release_year_internal(self, release_year: int): if release_year >= 1900 and type(release_year) is...
Add a method to RedBlackBST to print a RB-BST indexing the subnodes. Test the tree inserting...
Add a method to RedBlackBST to print a RB-BST indexing the subnodes. Test the tree inserting element by element and printing the results with (1) S E A R C H E X A M P L E (where the value is the index of the letter in the initial word) and (2) K R I S T E N public class RedBlackBST<Key extends Comparable<Key>, Value> { private Node root; private class Node // BST node with color bit (see...