Let's practice some trees!

Rick Flair y'all! Let's get it

Due Friday, 01-Nov (by 12:55pm)
For Extra credit (i.e., level 2 & 3): 05-Nov (by 11:55pm)

With this exercise, we are going to create the methods that support a `Binary Search Tree` class

Main function & code

Before we get too far, you can find some potentially usedful code to begin to test your tree

# Creates a BST (biinary search tree)
	print("Create binary search tree")
	new_root = BSTNode(6, "6")
	new_tree = BinarySTree()
	new_tree.bst_insert(new_root, BSTNode(5, "5"))
	new_tree.bst_insert(new_root, BSTNode(8, "8"))
	new_tree.bst_insert(new_root, BSTNode(3, "3"))
	new_tree.bst_insert(new_root, BSTNode(4, "4"))
	new_tree.bst_insert(new_root, BSTNode(9, "9"))
	new_tree.bst_insert(new_root, BSTNode(7, "7"))
	new_tree.bst_insert(new_root, BSTNode(2, "2"))
	new_tree.bst_insert(new_root, BSTNode(1, "1"))

	count = count_all_nodes(new_root)
	print("Print preorder")
	new_tree.preorder(new_root)
	print("Print postorder")
	new_tree.postorder(new_root)
	print("Print inorder")
	new_tree.inorder(new_root)
	print("Print levelorder")
	new_tree.levelorder(new_root)
	print("Count", count)

	print('Min', get_min(new_root))
	print('Max', get_max(new_root))

if __name__ == '__main__':
	main()

Class definition

Let's start with the main class definition. Below, we define a BSTNode class that represents each node in our tree & the constructor for the BinarySTree class.

The BSTNode class has three attributes (simplicity FTW!): key this reperesents something that allows us to search through the tre; data represents the value, data, etc. in the BSTNode; left is...YOU GUESSED IT...a pointer to the BSTNode (or None) to the left of the node; right is a pointer to the BSTNode (or None) to the right of the current node. Remember this is essentially pointing to a left & right subtree (which is key to think about when using recursion).

class BSTNode:
		def __init__(self, key, data):
				self.key = key
				self.data = data
				self.left = None
				self.right = None

class BinarySTree:
		''' Framework for a Tree class'''
		def __init__(self):
				self.root = None

Now, similar to past assignments, you get credit for the exercise as long as you submit your file with a clear reasonable effort on completing the methods.

However, with this assignment, we're going to have levels that mean you can get extra credit with the work.

Level 1 methods

If you complete these methods, you just get the normal 100%.

Traversal methods

First up is the traversal methods that we've reviewed in class. Notice we're taking a design decision that allows us to allow a user to call the method without specifying any particular node.

This allows us to completely hide or encapsulate the mechanisms that define the method.


# 6, 5, 3, 2, 1, 4, 8, 7, 9
def preorder(self):
	return self._preorder(self.root)

def _preorder(self, node):
	'''Prints a preorder traversal'''
	if node is not None:
				print(str([node.key, node.data]))
				preorder(node.left)
				preorder(node.right)

# 1, 2, 4, 3, 5, 7, 9, 8, 6
def postorder(self):
	return self._postorder(self.root)

def _postorder(self, node):
	'''Prints a postorder traversal'''
	pass

# 1, 2, 3, 4, 5, 6, 7, 8, 9
def inorder(self):
	return self._inorder(self.root)

def _inorder(self, node):
	'''Returns the string of an inorder traversal'''
	if node is not None:
		before = self._inorder(node.left)
		after = self._inorder(node.right)
		return before + ' ' + str(node.value) + ' ' + after
	else:
		return ""

Other level 1 methods

Next up we have two methods to define get_max & get_min

get_max should return the payload with the largest key in the BST (the key and value, not the BSTNode!)

get_min should return the payload with the smallest key in the BST (the key and value, not the BSTNode!)

def get_min(self):
	return self._get_min(self.root)

def _get_min(self, node):
	''' Return the smallest value in the BST'''
	pass

def get_max(self):
	return self._get_max(self.root)

def _get_max(self, node):
	'''Returns the max of a BST'''
	pass

Level 2 methods

If you correctly complete one of the following methods {search, get, get_size} AND one of the following methods {trim_bst, is_bst}, you get 2 points of extra credit. (The exercises are normally worth 1 point overall, so you're doubling the value).

Before you can get extra credit for completing any of these methods, you MUST complete all of the level 1 methods!!!

`search`, `get`, and `get_size`

The search method is used to tell us whether the tree contains a BSTNode that has a given value. This means it should return a Boolean.

The get method will look for a BSTNode in the tree that contains a given value and returns the first BSTNode that finds (which contains that value).

The get_size method returns the size of the tree (i.e., the number of BSTNodes in the Tree). We don't have a size attribute...because REASONS

def search(self, value):
	''' Return true if the tree contains the value given'''
	return self._search(self.root, value)

def _search(self, node, value):
	pass

def get(self, target):
	''' Returns the node object of a value'''
	return self._get(self.root, target)

def _get(self, node, target):
	pass

def get_size(self):
	''' Returns the number of nodes in the tree'''
	return self._get_size(self.root)

def _get_size(self, node):
	pass

`trim_bst`, `is_bst`

The trim_bst method trims the tree so that only BSTNodes with values in the range provided (inclusive) are kept. You are fine to edit the internal structure here (that is, the actual tree can be changed)
The is_bst method tells us whether we have an actual binary search tree. This method should return a Boolean

def trim_bst(self, min_val, max_val):
	'''Keep only the nodes in a BST that are beteween
	min_val and max_val'''
	self._trim_bst(self.root, min_val, max_val)

def _trim_bst(self, node, min_val, max_val):
	'''Traverse the tree
		 if we encounter a key less than our min_val, disregard that Node and
			only keep right subtree of that node
		 if we encounter a key greater than our max_val, disregard that Node and
			only keep left subtree of that node'''
	pass

# You might need to change this definition!
def is_bst(self, lastBSTNodeVal = -1):
	''' Returns True if the tree is a BST '''
	pass

Level 3 Methods

Welcome to the top!

Image from Black Mirror

If you correctly complete both methods below, you get an additional 1 point of extra credit

Before you can get extra credit for completing any of these methods, you MUST complete the requirements for level 2 extra credit!!!

I've already filled in the bst_insert method for you.

The level_order method should visit & print out each BSTNode (the key & value) level by level and from left to right on each level.
The remove method should be able to search for a BSTNode with a target value, remove that BSTNode. You must insure that you correctly reconnect your BSTNodes here!

def bst_insert(self, node):
	'''The Insert method is done for you!
	'''
	if self.root is None:
		self.root = node
	else:
		self._bst_insert(self.root, value)

def _bst_insert(self, root, node):
	'''
		Inserts a node into the binary search tree so that it still keeps the
		 structure property of a binary search tree
		 (nodes in left child subtrees have keys < parent node key;
			nodes in right child subtrees have keys > parent node key)
		 If a node w/ same key is already in tree, we ignore the insertion
		'''
		if root.key > node.key:
						if root.left is None:
								root.left = node
						else:
								_bst_insert(root.left, node)
				else:
						if root.right == None:
								root.right = node
						else:
								_bst_insert(root.right, node)

# 6, 5, 8, 3, 7, 9, 2, 4, 1
def level_order(self,node, more=None):
	'''Prints a level order traversal, you can change this method definition if you need/want to!'''
	pass

def remove(self, target):
	''' Remove a target from a binary tree
	HINT: You'll need a find predecessor/successor function
	'''
	pass