Week 7: Exercises

1. Prepend

You are given a class LinkedList with an attribute head that points to the head of a linked list of Node objects:

class LinkedList:
    def __init__(self, head):
        self.head = head

Write a method that prepends a value to a LinkedList.

2. Append

Write a method that appends a value to a LinkedList.

3. Delete First

Write a method that deletes the first node (if any) in a LinkedList.

4. Delete Last

Write a method that deletes the last node (if any) in a LinkedList.

5. Split a List

Write a function split() that takes a pointer to the the first Node in a linked list and splits the list into two linked lists of roughly equal size. Return a pair containing these lists. The elements in the returned lists may appear in any order.

6. Merge Lists

Write a function merge() that takes pointer to the first Nodes of two sorted lists and combines them into a single sorted list.

7. Linked List Merge Sort

Write a function merge_sort() that performs a merge sort on a linked list, returning a pointer to a sorted list. Do not allocate any new list nodes while sorting.

8. Complete Tree

Write a function completeTree(h) that builds a complete binary tree of height h. Every node's value should be that node's depth.

9. Mirror Image

Write a function mirror(t) that modifies a binary tree, flipping it from left to right so that it looks like a mirror image of the original tree.

10. Ancestor Check

Write a function isAncestor(p, q) that takes pointers to two nodes p and q in a binary tree and returns true if p is an ancestor of q.

11. Tree Compare

Write a function equal(t, u) that takes two Node objects representing the roots of two binary trees. The function should return True if the binary trees are identical, i.e. they have the same structure and the same values in corresponding nodes.

12. Complete Tree

Write a function that takes a binary tree and returns True if the tree is complete.