A document from MCS 275 Spring 2023, instructor David Dumas. You can also get the notebook file.

MCS 275 Spring 2023 Homework 8

  • Course Instructor: David Dumas

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work.

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday March 7, 2023.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Content

This assignment is about trees.

Resources you may consult

Most relevant:

Less likely to be relevant, but also allowed:

Point distribution

This homework assignment has 2 problems, numbered 2 and 3. The grading breakdown is:

Points Item
3 Autograder
6 Problem 2
6 Problem 3
15 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 2: Common ancestor

If x and y are two nodes of the same binary tree (as Node objects), then the root node is an ancestor of both of them (or is equal to one or both of them). So we see that any two nodes in a binary tree have a common ancestor.

Furthermore, any two nodes have a unique lowest common ancestor, i.e. the node a that is a common ancestor of both x and y, and such that no child of a is an ancestor of both x and y. Another way to describe a is that if you take the path in the tree that starts at x and ends at y, then a is the node on that path that is closest to the root. (And it's possible that a might be equal to x or to y, if one of x and y is an ancestor of the other.)

Write a function lowest_common_ancestor(x,y) that takes two Node objects x and y and returns their lowest common ancestor (another Node object). If there is no common ancestor (i.e. if x and y lie in different trees), return None.

Submit this function in a file hwk8prob2.py.

Problem 3: Ideal BST insert order

A binary tree with $(2^n-1)$ nodes can be "perfect" or "full" in the sense that it has as many nodes as possible for its depth. Here are some pictures of full binary trees:

Now suppose we insert the integers $1$, $2$, ... $2^n-1$ into a binary search tree. We might get a full tree, or might not, depending on the order:

Write a function ideal_insert_order(n) that returns a list containing the integers from $1$ to $2^n-1$ (inclusive) in an order so that inserting them into a BST in that order results in a full tree.

For example, ideal_insert_order(3) might return [4,2,1,3,6,5,7]. (There are many other possible correct answers. But for example returning [1,2,3,4,5,6,7] would be wrong: Inserting in that order doesn't give a full tree.)

It's important your function works for any n (subject only to limits imposed by time, memory, and/or recursion depth) and is not hard-coded to work only for a single value or a few of them.

Submit this function in a file hwk8prob3.py.

Revision history

  • 2023-03-03 Initial publication