Continuing my interview prep journey i’d like to tackle a specific data structure in the tree family. Tree’s ordinarily are data structures that can have between 0-N children and all generate from a specific root. (Tree’s honestly look more like a trees root structure than the actual tree, but tree sounds better). Trees have a variety of uses and applications (A specific example is the DNS system used for addressing domain names) and are an important data structure to learn.<\/p>\n\n\n\n
There are a few subclasses of the tree, but one important one is the binary search tree. A binary search tree is a tree where each child has at most two children. The left child is always less than the parent node and the right child is always greater than the parent node. If you traverse the tree any node within the tree will also be a binary search tree. What makes this structure so powerful is its ability to make a search for a specific value O(log N) time.<\/p>\n\n\n\n
Similar to a linked list, a binary search tree is constructed of nodes that reference one another. The base level is called the root which is contained in the tree code. (The following examples and methods will be done in Python3)<\/p>\n\n\n\n
class Node:\n \n def __init__(self, key):\n self.key = key\n self.left = None\n self.right = None\n\nclass BinarySearchTree:\n \n def __init__(self):\n self.root = None\n<\/code><\/pre>\n\n\n\n These are the bare essentials for the binary search tree. The Node class for holding the node values and the BinarySearchTree class for performing all of the operations of the binary search tree.<\/p>\n\n\n\n
Insertion<\/h2>\n\n\n\n
The first operation we want to perform with a binary search tree is to insert new nodes. <\/p>\n\n\n\n
class BinarySearchTree:\n \n def __init__(self):\n self.root\n\n def insert(self, key):\n if self.root is None:\n self.root = Node(key)\n else:\n current = root\n parent = None\n\n while True:\n parent = current\n\n if key < parent.key:\n current = current.left\n \n if current is None:\n parent.left = Node(key)\n return\n \n else:\n current = current.right\n \n if current is None:\n parent.right = Node(key)\n return\n <\/code><\/pre>\n\n\n\n What happens in the code. We first check the root to ensure that there is a Node assigned. If there is we can traverse down the tree by comparing the value of our new key against the parent node until we find an open spot.<\/p>\n\n\n\n
Search<\/h2>\n\n\n\n
Search is very simple. You compare the values from left and right until you either find the value or find None.<\/p>\n\n\n\n
def search(self, target):\n current = self.root\n\n while current is not None:\n if current.key == target:\n return True\n else:\n if current.key > target:\n current = current.left\n else:\n current = current.right\n return False<\/code><\/pre>\n\n\n\nDelete<\/h2>\n\n\n\n
Deleting is a little more complex depending on which node is deleted. <\/p>\n\n\n\n
def delete(self, target):\n if root is None:\n return\n\n self.root = self.delete_helper(self.root, target)\n\ndef getMinimumKey(self, current):\n while current.left:\n current = current.left\n return current\n\ndef delete_helper(self, root, target):\n \n parent = None\n current = root\n\n while current and current.key != target:\n parent = current\n \n if target < current.key:\n current= current.left\n else:\n current = current.right\n \n current is None:\n return root\n\n # Case 1: No Children\n if current.left is None and current.right is None:\n \n if current != root:\n if parent.left == current:\n parent.left = None\n else:\n parent.right = None\n else:\n root = None\n\n # Case 2: node to be deleted has two children\n elif current.left and current.right:\n \n successor = self.getMinimumKey(current.right)\n \n val = successor.key\n \n self.delete_helper(root, successor.key)\n\n current.key = val\n\n # Case 3: node to be deleted has only one child\n else:\n \n if current.left:\n child = current.left\n else:\n child = current.right\n\n if current != root:\n if current = parent.left:\n parent.left = child\n else:\n parent.right = child\n else:\n root = child\n\n return root<\/code><\/pre>\n\n\n\n There are three cases to look out for when deleting a node. If the node has no children, the node has one child, and the node has two children. In case 1, where the node has no children such as a leaf node or a root node with no children. We simply set the side that the child is on to None or the root to None if we are deleting a root with no children. If the node has one child we figure out where the child is (left or right) and then we assign that child to the now open position on the current nodes parent to the child, or set the root to the child. For two children it gets slightly more complicated. The child that needs to replace a two child parent is the parents in order successor or the right child’s left most child. I added another helper method that finds this child and then once it is found it will apply the deletion and replacement.<\/p>\n\n\n\n
Traversals<\/h2>\n\n\n\n
Traversals involve how to navigate through the tree. They also come up in interview questions (there is a famous one where you need to build a correct tree with a pre-order and in-order array). There are three types, pre-order, in-order, and post-order. Each of the traversals deals with which node gets processed first when navigating through the tree. All operations are performed in O(N) time (because you need to find every node).<\/p>\n\n\n\n
For my design of the traversals I’m focusing on their utility in the testing process. I’ll create an array that will be returned and test that array to ensure the traversal gives the right result.<\/p>\n\n\n\n
In Order Traversal<\/strong>:
In order traversal is the easiest to comprehend. When you finish with this traversal it should return the values from least to greatest as it is processing the nodes in order. (For the sake of space, all of these methods are within the BinarySearchTree, but I will show them on their own.)<\/p>\n\n\n\ndef in_order_traversal(self):\n traversal_list = []\n return self.in_order_traversal_helper(self.root, traversal_list\n\ndef in_order_traversal_helper(self, root, traversal_list):\n if root is None:\n return\n self.in_order_traversal_helper(root.left, traversal_list)\n traversal_list.append(root.key)\n self.in_order_traversal_helper(root.right, traversal_list)\n \n return traversal_list<\/code><\/pre>\n\n\n\n You’ll notice that in_order_traversal_helper() is just a depth first search that appends the values to an array and returns that array. If I had a tree with 2 as the root, 1 as the left node, and 3 as the right node if I perform an in-order traversal, I will get an array that will look like [1, 2, 3]<\/p>\n\n\n\n
Pre-order Traversal<\/strong>
Pre-order traversal processes a node as soon as it is reached and then moves along the left and right sub trees. Since the root is always the first node in the list. Pre-order traversal’s can be useful for constructing a correct tree from an array. Note that the traversals are all very similar, what separates them is the order in processing nodes.<\/p>\n\n\n\ndef pre_order_traversal(self):\n traversal_list = []\n return pre_order_traversal_helper(root, traversal_list)\n\ndef pre_order_traversal_helper(self, root, traversal_list)\n if root is None:\n return\n\n traversal_list.append(root.key)\n self.pre_order_traversal_helper(root.left, traversal_list)\n self.pre_order_traversal_helper(root.right, traversal_list)\n\n return traversal_list<\/code><\/pre>\n\n\n\n This will add the node to the array as soon as it is reached, and then move on to the left then right sub trees. Given the same tree as before (root=2, left=1, right=3) this will return an array [2, 1, 3]<\/p>\n\n\n\n
Post-order traversal<\/strong>
<\/strong>Post order traversal involves going all the way to the furthest leaf within the tree then processing it. The array will be filled with all the leaf nodes starting from left to right, then the parents, all the way until the root.<\/p>\n\n\n\ndef post_order_traversal(self):\n traversal_list = []\n return self.post_order_traversal_helper(root, traversal_list)\n\ndef post_order_traversal_helper(self, root, traversal_list):\n if root is None:\n return\n \n self.post_order_traversal_helper(root.left, traversal_list)\n self.post_order_traversal_helper(root.right, traversal_list)\n traversal_list.append(root.key)\n\n return traversal_list<\/code><\/pre>\n\n\n\n Given the same tree (root=2, left=1, right=3) we get an array returned [1, 3, 2]<\/p>\n\n\n\n
Those are the basic operations of a binary search tree. There are more advanced BST’s that also self balance (which I may or may not cover in a future blog post) that cover for disadvantages of the binary search tree (what if all the inserted nodes are on the right or left of the tree?). With the basics of the tree down we can get a better idea of how to navigate BST problems and possible ways to use a BST to solve common problems.<\/p>\n","protected":false},"excerpt":{"rendered":"
Continuing my interview prep journey i’d like to tackle a specific data structure in the tree family. Tree’s ordinarily are data structures that can have between 0-N children and all generate from a specific root. (Tree’s honestly look more like a trees root structure than the actual tree, but tree sounds better). Trees have a […]<\/p>\n","protected":false},"author":2537,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-66","post","type-post","status-publish","format-standard","hentry","category-uncategorized","missing-thumbnail"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/posts\/66","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/users\/2537"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/comments?post=66"}],"version-history":[{"count":8,"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/posts\/66\/revisions"}],"predecessor-version":[{"id":74,"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/posts\/66\/revisions\/74"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/media?parent=66"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/categories?post=66"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/techwithchris\/wp-json\/wp\/v2\/tags?post=66"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}