Work in hwk7prob2.py. Import the module trees (trees.py).
Write a function forest_roots(...) that takes one argument, node_list, which is a list of Nodes. These nodes might all be in the same binary tree, or they may be scattered across several different trees. The function should return a list of the root nodes of all the trees that contain some node from node_list. Each root node should only be listed once.
Example behavior:
If node_list is empty: returns [] (empty list)
If all nodes in node_list lie in the same binary tree: returns [ R ] where R is the root node of that tree.
If node_list = [A1,A2,B] where A1 and A2 are siblings and B lies in a different binary tree, returns [ RA, RB ] where RA is the root of the tree containing A1 and A2 and RB is the root of the tree containing B.
Make sure to give the function a descriptive docstring.
def root_node(x):
"""
Pass from node `x` to parent repeatedly until
the root is found
"""
if x.parent == None:
return x
else:
return root_node(x.parent)
def forest_roots(node_list):
"""
Return a list of distinct root nodes for the trees
containing the nodes in `node_list`.
"""
roots_list = []
for x in node_list:
r = root_node(x)
if r not in roots_list:
roots_list.append(r)
return roots_list
Work in hwk7prob3.py. Import the module trees (trees.py).
The edges of a tree are all the pairs of nodes (p,c) where p is the parent of c. (If you draw a picture of the tree, then there is one straight line in your picture for each such pair.)
Suppose you have a binary search tree (BST) with keys that are integers. Let's say that an edge (p,c) is an increment edge if the keys of p and c differ by one. That is, either c is the left child of p and c.key+1 == p.key or c is the right child of p and p.key+1 == c.key.
Write a function num_increment_edges(T) that takes the root node T of such a BST and returns the number of increment edges. You can use any method you like (e.g. recursion or iteration).
Make sure to give the function a descriptive docstring.
def num_increment_edges(T):
"""
Count the number of edges in BST `T` that join two
nodes whose keys differ by one.
"""
if T.key == None:
return 0
n = 0
k = T.key
if T.left != None:
# There's an edge to left; maybe it is an increment edge
if T.left.key == k-1:
n += 1 # Yes, so count it
# Now count any edges in the left subtree
n += num_increment_edges(T.left)
if T.right != None:
# There's an edge to right; maybe it is an increment edge
if T.right.key == k+1:
n += 1 # Yes, so count it
# Now count any edges in the right subtree
n += num_increment_edges(T.right)
return n