Question

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:

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.

"""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 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 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 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 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, 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:
⦁ 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 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 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 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...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 2 minutes ago

asked 11 minutes ago

asked 11 minutes ago

asked 15 minutes ago

asked 23 minutes ago

asked 24 minutes ago

asked 26 minutes ago

asked 32 minutes ago

asked 32 minutes ago

asked 48 minutes ago

asked 48 minutes ago

asked 51 minutes ago