MCS 275 Spring 2023 Homework 8 Solutions¶

def ancestors(x):
    """
    Given node, returns list containing its parent, its parent's parent, etc.
    """
    L = [x]
    while L[-1].parent != None: # While we can find a parent of the most recently-found parent
        L.append(L[-1].parent) # Put parent into the list
    return L

def lowest_common_ancestor(x,y):
    """
    Given nodes `x` and `y`, returns common ancestor of x, y that has shortest distance to x and y
    """
    # Pre-compute ancestors for each node (so we don't have to call ancestors() many times in a loop)
    ancestors_x = ancestors(x)
    ancestors_y = ancestors(y)
    
    # Since ancestors are in order, the first match we find must be the lowest common ancestor
    for node in ancestors_x:
        if node in ancestors_y:
            return node
    
    # If no common ancestor is found, return None
    return None

def ideal_insert_order1(n, keys = None):
    """
    An approach inspired by mergesort. Initialize a list of keys called `keys`. At 
    each step take the middle element of `keys` and put it in a list `L`. Then extend
    L by making recursive calls on everything to the left of L and everything to the
    right.
    """
    if keys is None:
        keys = list(range(1, 2**n))
        
    if len(keys) <= 1: # Base case
        return keys
    
    middle = len(keys)//2
    L = [keys[middle]] # Insert the "middle" key 
    
    # Split the list down the middle and make a recursive call on each side
    L += ideal_insert_order1(n, keys[:middle])
    L += ideal_insert_order1(n, keys[middle+1:])
    
    return L

# The most accessible recursive solution based on
# recognizing a pattern in ideal insert orders:
def ideal_insert_order2(n):
    """
    Find order of insertion for integers 1...2**n-1 that results in a full
    binary tree. Do so by making a list of those integers where the first
    element of the list is the median, and where dividing the rest into two
    halves `A` and `B` gives:
    * Every element of `A` is less than the median
    * Every element of `B` is greater than the median
    * All the conditions in this list hold for `A`
    * All the conditions in this list hold for `B`
    This ensures that when the first element is used as the root, all of `A`
    ends up in the left subtree and all of `B` ends up in the right subtree. In
    particular the left and right subtrees contain the same number of elements.
    That this is recursively true at each stage (with each subtree having 2**k-1
    elements for some k) ensures the resulting tree is full.
    """
    if n == 1:
        return [1]
    L = ideal_insert_order2(n - 1)
    return [2 * L[0]] + L + [2 * L[0] + x for x in L]
# power of two-^       part     part shifted by constant

from trees import Node

def depth(T):
    """
    Depth of a binary tree (in edges). Could use the method requested in
    worksheet 8 instead, if present.
    """
    if T == None:
        # returning -1 here means we cancel count of edge
        # that leads to an absent child.
        return -1
    return 1 + max(depth(T.left), depth(T.right))


def blank_full_tree(d, parent=None):
    """
    Create a full binary tree of depth `d`.  If given, `parent` sets the parent
    of the root node of that tree. Returns the root node.
    """
    if d < 0:
        return None
    n = Node(parent=parent)
    n.left = blank_full_tree(d - 1, parent=n)
    n.right = blank_full_tree(d - 1, parent=n)
    return n


def inorder_nodes(T):
    """
    Do an inorder traversal of binary tree `T` and return a list of node objects
    in the order visited. This is very similar to `Node.inorder` except that it
    returns the nodes themselves rather than just the keys.
    """
    if T == None:
        return []
    return inorder_nodes(T.left) + [T] + inorder_nodes(T.right)


def ideal_insert_order3(n):
    """
    Find order of insertion for integers 1...2**n-1 that results in a full
    binary tree. Do so by making a full tree that has no keys (all are None),
    then traversing it inorder and adding keys that are ascending integers as we
    go. Then the list of keys seen in a preorder traversal will provide a way to
    duplicate the tree, i.e. an ideal insertion order.
    """
    # Make an full tree with all keys `None`
    T = blank_full_tree(n - 1)
    # Fill it with integers 1..2**n-1 in way so that
    # it is a valid BST (i.e. preorder = ascending order)
    for i, node in enumerate(inorder_nodes(T)):
        node.key = i + 1
    N = 2 ** n - 1
    assert i + 1 == N  # check that we had the expected number of nodes!
    # Now the preorder is an insert order that will reproduce the
    # tree!
    return T.preorder()

def ideal_insert_order4(n):
    """
    Find order of insertion for integers 1...2**n-1 that results in a full
    binary tree. It turns out that one such order is obtained by the following:
    * List all the integers (e.g. 1,2,3,4,5,6,7)
    * Sort by the number of `1` bits when the number is represented in binary (low to high)
      e.g. 1=0b001, 2=0b010, 4=0b001, 3=0b110, 5=0b101, 6=0b011, 7=0b111
    * Within numbers with the same `1`-bit count, sort by the corresponding
      numeric value, but in decreasing order.
      e.g. [#1bits = 1]  4=0b100, 2=0b010, 1=0b001,
           [#1bits = 2]  6=0b110, 5=0b101, 3=0b011,
           [#1bits = 3]  7=0b111
    * Return the associated order of the integers e.g. 4, 2, 1, 6, 5, 3, 7

    We don't mean to imply that this is an easily discoverable characterization,
    nor that it's within the scope of MCS 275. But when combined with some
    built-in constructions (like binary conversion, anonymous functions,
    range(), sorting with custom order, etc.) it yields a solution in one
    statement. That's why we choose to show it here.

    HOWEVER, note this doesn't return the same list as `ideal_insert_order1` and
    `ideal_insert_order2`.  There are many possible ideal insert orders, as the
    assignment explains.
    """
    return sorted(
        range(1, 2 ** n),  # integers 1..2**n-1
        key=lambda k: (  # sort by tuple
            bin(k).count("1"),  # count 1-bits in binary
            -k,  # secondary factor: sort by numeric value, decreasing
        ),
    )

import trees
import treevis

# List of solutions we're checking
iio_fns = [
    ideal_insert_order1,
    ideal_insert_order2,
    ideal_insert_order3,
    ideal_insert_order4
]

n = 4

for iio in iio_fns:
    print("TESTING SOLUTION:",iio.__name__)
    T = trees.BST()
    for node in ideal_insert_order1(n):
        T.insert(node) # Insert nodes in the order given by our function
    
    print("The nodes we want to insert are: {}".format(list(range(1, 2**n))))
    print("The resulting tree is:")
    treevis.treeprint(T)
    print()