MCS 275 Spring 2023 Homework 8¶

• Course Instructor: Emily 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:

• Worksheet 8 Solutions
• Lecture 16 - Trees
• Lecture 17 - BST
• Lecture 18 - Traversals
• Chapter 7 of Miller and Ranum
• trees.py
• treevis.py
• treeutil.py
• treeutil documentation
• Sample programs
• Downey's book
• MCS 260 course materials from Fall 2021:
  • Slides, homework, worksheets, and projects
  • Sample programs

Less likely to be relevant, but also allowed:

• Any other lecture of MCS 275 spring 2023.
• Python tour
• Slides from any lecture of my most recent MCS 260 course MCS 260, Fall 2021.
• Any lecture video posted on our course Blackboard site
• Downey's book
• Any other textbook listed on the course blackboard site under "Textbooks"

Point distribution¶

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

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