{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 275 Spring 2022 Worksheet 8 Solutions\n",
"\n",
"* Course instructor: David Dumas\n",
"* Solutions prepared by: Johnny Joyce, Jennifer Vaccaro"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Topics\n",
"The main topics of this worksheet are:\n",
"* Trees\n",
"* Binary search trees\n",
"\n",
"\n",
"## Resources\n",
"\n",
"These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.\n",
"\n",
"* [Lecture 19 - Trees](http://dumas.io/teaching/2022/spring/mcs275/slides/lecture19.html)\n",
"* [Lecture 20 - BST](http://dumas.io/teaching/2022/spring/mcs275/slides/lecture20.html)\n",
"* [Lecture 21 - Traversals](http://dumas.io/teaching/2022/spring/mcs275/slides/lecture21.html)\n",
"* [Chapter 7 of Miller and Ranum](https://runestone.academy/runestone/books/published/pythonds/Trees/toctree.html)\n",
"* [Downey's book](https://greenteapress.com/thinkpython2/html/)\n",
"\n",
"The most useful files from the sample code repository are:\n",
"* [trees.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/trees.py)\n",
"* [treevis.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/treevis.py)\n",
"* [treeutil.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/treeutil.py)\n",
"* [treeutil documentation](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/treeutil.md)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 1. Node relationship\n",
"\n",
"Suppose you have two `Node` objects (or objects of a subclass of `Node`) as defined in (https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/trees.py). Let's call them `x` and `y`. You might ask how they are related to one another, if it all. In general, exactly one of the following statements will be true:\n",
"1. The nodes are equal\n",
"1. One of the nodes is an ancestor of the other\n",
"1. The nodes lie in the same tree, but neither is an ancestor of the other\n",
"1. The nodes do not lie in the same tree\n",
"\n",
"Write a function `node_relationship(x,y)` that takes two nodes and returns one of these strings:\n",
"1. `\"equal\"`\n",
"1. `\"ancestor\"`\n",
"1. `\"cousin\"`\n",
"1. `\"unrelated\"`\n",
"\n",
"according to which of the cases listed above describes the relationship between `x` and `y`.\n",
"\n",
"(Note that the use of \"cousin\" to describe case (3) doesn't fit the genealogical analogy perfectly, as it would also include the case of siblings.)\n",
"\n",
"Also, make test cases for your function that generate each of the possible answers."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution 1:\n",
"\n",
"Uses a helper function `parents` to find all parents, grandparents, great-grandparents, etc."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def parents(x)\n",
" '''\n",
" Given node, returns list containing its parent, its parent's parent, etc.\n",
" '''\n",
" L = [x]\n",
" while L[-1].parent != None: # While we can find a parent of the most recently-found parent\n",
" L.append(L[-1].parent) # Put parent into the list\n",
" return L\n",
" \n",
"def node_relationship(x,y):\n",
" \"\"\"\n",
" Returns string repesenting genealogical relationship between nodes x and y\n",
" \"\"\"\n",
" \n",
" if x == y:\n",
" return \"equal\"\n",
" \n",
" # Find all parents of x (including its grandparent, great-grandparent, etc.)\n",
" parents_x = parents(x)\n",
" # Find all parents of y\n",
" parents_y = parents(y)\n",
" \n",
" if x in parents_y:\n",
" return \"ancestor\"\n",
" \n",
" if y in parents_x:\n",
" return \"ancestor\"\n",
" \n",
" # Last item in each list is root of tree.\n",
" if parents_x[-1] == parents_y[-1]:\n",
" return \"cousins\"\n",
" \n",
" # If no previous attempts to find relationship worked, then x and y are unrelated.\n",
" return \"unrelated\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution 2:\n",
"\n",
"Slightly shorter version using keys of nodes. **Can fail** if given nodes in two separate trees which contain the same key at some point, so avoid reusing code from this version"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def node_relationship(x,y):\n",
" \"\"\"\n",
" Returns string repesenting genealogical relationship between nodes x and y\n",
" \"\"\"\n",
" \n",
" if x.key == y.key:\n",
" return \"equal\"\n",
" \n",
" if x.search(y.key) != None: # If y can be found \"below\" x\n",
" return \"ancestor\"\n",
" \n",
" if y.search(x.key) != None: # If x can be found \"below\" y\n",
" return \"ancestor\"\n",
" \n",
" # Find the root of x's tree\n",
" root_x = x\n",
" while root_x.parent != None: # Keep ascending tree until root is found\n",
" root_x = root_x.parent\n",
" \n",
" if root_x.search(y.key) != None: # If y can be found anywhere in x's tree\n",
" return \"cousin\"\n",
" \n",
" # If no previous attempts to find relationship worked, then x and y are unrelated.\n",
" return \"unrelated\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Get ready to edit `trees.py`\n",
"\n",
"The rest of the worksheet focuses on adding features to the module `trees.py` from lecture. To prepare for that, download these files and save them in a directory where you'll work on worksheet 8.\n",
"* [trees.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/trees.py)\n",
"* [treevis.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/treevis.py)\n",
"* [treeutil.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/treeutil.py)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Know how to test your code\n",
"\n",
"It will be hard to test your code if you don't have any search trees to test it with. To that end, I created a module `treeutil.py` (which you were asked to download above) that will generate random binary search trees on request. It can also give a random node of the tree, or a random pair of nodes.\n",
"\n",
"Open the full documentation of the module in a separate browser tab, and keep it open as you work:\n",
"* [treeutil documentation](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/trees/treeutil.md)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2. Minimum and maximum\n",
"\n",
"Add two new methods, `minimum` and `maximum` to the `BST` class for finding the node with the smallest or largest key in the subtree that has this node as its root."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution\n",
"\n",
"In `trees.py` under the `BST` class:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\n",
" def minimum(self):\n",
" \"\"\"\n",
" In the subtree that this node is the root of, find and\n",
" return the the smallest key.\n",
" \"\"\"\n",
"\n",
" if self.left != None: # Try to return the min of the left side first (left side is always smaller)\n",
" return self.left.minimum()\n",
"\n",
" else: # Otherwise, no need to look at right side (because it must be bigger)\n",
" return self.key"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
" def maximum(self):\n",
" \"\"\"\n",
" In the subtree that this node is the root of, find and\n",
" return the the largest key.\n",
" \"\"\"\n",
" \n",
" if self.right != None: # Try to return the max of the right side first (right side is always bigger)\n",
" return self.right.minimum()\n",
"\n",
" else: # Otherwise, no need to look at left side (because it must be smaller)\n",
" return self.key"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3. Depth\n",
"\n",
"Add a method `depth` to the `BST` class that computes the depth of the tree (optionally starting at a certain node rather than the root)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"# This should go inside class `BST` in `trees.py`\n",
" def depth(self, start_node = None):\n",
" \"\"\"\n",
" Return the length (in number of edges) of the longest descending path starting\n",
" from the node `start_node`. If `start_node` is not given, starts from root node.\n",
" \"\"\"\n",
" # If user gave optional argument for starting point\n",
" if start_node != None:\n",
" initial = self.search(start_node)\n",
" return initial.depth()\n",
"\n",
" # Base case: if there are no child Nodes, cannot go any further down\n",
" if self.left == None and self.right == None:\n",
" return 0\n",
"\n",
" # Cases where only one child Node is defined\n",
" if self.right == None:\n",
" return self.left.depth() + 1 # Add 1 to account for increased depth\n",
" elif self.left == None:\n",
" return self.right.depth() + 1 # Add 1 to account for increased depth\n",
"\n",
" # Last case: both left and right child Nodes are defined\n",
" else:\n",
" # Note this is the built-in `max` function, not the one we wrote in Q2\n",
" return max(self.left.depth(), self.right.depth()) + 1 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 4. Interval of a node\n",
"\n",
"Suppose you are given a binary search tree `T` and a node `x` that has no children. If you change the key of `x`, the tree may or may not be a binary search tree.\n",
"\n",
"Here's an example to illustrate this. Consider this BST:\n",
"```\n",
" [15]\n",
"\n",
" [9] [29]\n",
"\n",
"[5] [12]\n",
"```\n",
"If `x` is the node with key 12, then changing the key to 13 still gives a binary search tree:\n",
"```\n",
" [15]\n",
"\n",
" [9] [29]\n",
"\n",
"[5] [13]\n",
"```\n",
"But if we change the key to 6, the result is not a binary search tree; the right subtree of the node with key 9 contains keys smaller than 9:\n",
"```\n",
"❌THIS IS NOT A BST❌\n",
" [15]\n",
"\n",
" [9] [29]\n",
"\n",
"[5] [6]\n",
"```\n",
"And if we change the key to 18, the result is not a binary search tree. The left subtree of the root node contains a node with key larger than 15:\n",
"```\n",
"❌THIS IS NOT A BST❌\n",
" [15]\n",
"\n",
" [9] [29]\n",
"\n",
"[5] [18]\n",
"```\n",
"\n",
"Now, if you look more closely at this example, you can convince yourself that the key 12 can be changed to any number in the closed interval $[9,15]$ while keeping the BST condition, but that anything outside of this range will result in a non-BST. This is called the **interval** of the node.\n",
"\n",
"Add a method to `BST` that can be called whenever the node has no children, and which returns a tuple `(kmin,kmax)` where `kmin` and `kmax` are the smallest and largest values (respectively) that the key of that node could be changed to while keeping the BST condition. In some cases, there may be no lower or upper limit, in which case the value `None` should be returned for `kmin`, `kmax`, or both. If called on a node that has children, it should raise an exception.\n",
"\n",
"Use this method definition:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# This should go inside class `BST` in `trees.py`\n",
" def interval(self):\n",
" \"\"\"\n",
" If this node has no children, return the minimum and maximum key values that\n",
" could be given to this node without violating the BST condition. The value None\n",
" is used to indicate that the range of allowable values has no upper or lower\n",
" bound.\n",
" \"\"\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For example, in this tree:\n",
"```\n",
" [15]\n",
"\n",
" [9] [29]\n",
"\n",
"[5] [12]\n",
"```\n",
"calling `.interval()` on its nodes will result in the following return values:\n",
"```\n",
"[15] : (raises exception because the node has children)\n",
" [9] : (raises exception because the node has children)\n",
" [5] : None,9\n",
"[12] : 9,15\n",
"[29] : 15,None\n",
"```\n",
"\n",
"Finally, it may be helpful in this problem to recall that functions in Python can return multiple values, and if they do, the returned values are assembled into a tuple. That means the two statements below do the same thing:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
" return 1,2,3\n",
" return (1,2,3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
" def interval(self):\n",
" \"\"\"\n",
" If this node has no children, return the minimum and maximum key values that\n",
" could be given to this node without violating the BST condition. The value None\n",
" is used to indicate that the range of allowable values has no upper or lower\n",
" bound.\n",
" \"\"\"\n",
" if self.left != None or self.right != None:\n",
" raise ValueError(\"Method `interval` may only be used on nodes with no children\")\n",
" \n",
" # Left and right sides of interval to be returned\n",
" interval_left = None\n",
" interval_right = None\n",
"\n",
" if self.parent == None: # If we are at the root of the tree, then interval is unlimited\n",
" return (interval_left, interval_right)\n",
"\n",
" # If current node is to the parent's left\n",
" if self.parent.left.key == self.key:\n",
" interval_right = self.parent.key # Upper bound is given by parent's key\n",
" if self.parent.parent != None:\n",
" grandparent = self.parent.parent\n",
" # Check if parent is to the right of its own parent\n",
" if grandparent.right.key == self.parent.key:\n",
" # If so, then parent's parent's key is lower bound\n",
" interval_left = grandparent.key\n",
" \n",
" # Else, current node is to the parent's right\n",
" else:\n",
" interval_left = self.parent.key # Lower bound is given by parent's key\n",
" if self.parent.parent != None:\n",
" grandparent = self.parent.parent\n",
" # Check if parent is to the left of its own parent\n",
" if grandparent.left.key == self.parent.key:\n",
" # If so, then parent's parent's key is upper bound\n",
" interval_right = grandparent.key\n",
" \n",
" return (interval_left, interval_right)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Code to test the tree using the given example:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" [15]\n",
"\n",
" [9] [29]\n",
"\n",
"[5] [12] . .\n",
"\n",
"Interval of [5]: (None, 9)\n",
"Interval of [12]: (9, 15)\n",
"Interval of [29]: (15, None)\n"
]
}
],
"source": [
"import treevis\n",
"import treeutil\n",
"\n",
"T = treeutil.BST(15)\n",
"T.insert(9)\n",
"T.insert(29)\n",
"T.insert(5)\n",
"T.insert(12)\n",
"treevis.treeprint(T)\n",
"\n",
"for key in [5, 12, 29]: # Check interval of each of: 5, 12, and 29\n",
" node = T.search(key)\n",
" print(\"Interval of {}: {}\".format(node, node.interval()))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Challenge\n",
"\n",
"This is an extra activity to work on if you finish all the exercises above. This won't be included in the worksheet solutions.\n",
"\n",
"Given a node `x` in a BST, you might want to know its **successor**, meaning the node whose key is larger than `x` but as small as possible given that condition. (We'll assume in this problem that all nodes in the tree have distinct keys).\n",
"\n",
"It turns out that there is an efficient description of the successor as follows:\n",
"* If `x` has a right child, then the successor is the smallest key in the right subtree of `x`\n",
"* If `x` does not have a right child, but has a successor, then the successor is an ancestor of `x`. If you visit these ancestors by traveling upward from `x`, then the first node you reach that is the left child of its parent is the successor.\n",
"* If `x` has no right child, and if moving up from `x` to the root only ever visits nodes that are right children of their parents, then `x` is the maximum of the tree, so it has no successor.\n",
"\n",
"Write a method `successor` of class `BST` that finds and returns the successor of a node, or returns `None` if there is no successor."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Revision history\n",
"\n",
"* 2022-02-26 - Initial publication"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}