Assignment #3 - Trees and Binary Search Trees

Due July 14, 2009 1pm

(You must submit electronically as well as submit a printed copy to the drop box in BA2220.)

Notes + Starter Code

For part 3 only, you may use python's built-in sorting functionality. You may assume that python's built-in sort function has time complexity O(n log n), where n is the number of elements being sorted.

Part 1 - Reversing The Order of Leaves

We define the order of leaves in a binary tree T to be the order in which leaves are visited in a preorder traversal of T.

Write a function reverse_leaves(tree) that takes a BinaryTree instance as an argument and returns a new BinaryTree instance that is identical to the original except that the order of its leaves is reversed. That is, the order in which leaves are visited in a preorder traversal of the returned tree should be the reverse of the order in which they are visited in a preorder traversal of the original tree, but the structure of the tree should otherwise be exactly the same as the original tree and the labels on all internal nodes should remain unchanged. The original tree that was passed as an argument should not be modified.

Your implementation should have time complexity O(n), where n is the number of nodes in the tree.

Example. Suppose you are given the tree:

    10
   /  \
  90   35
 / \     \
12  5     8
   /
  6

    10
   /  \
  90   35
 / \     \
8  5      12
   /
  6

Question: Suppose we change the definition of the order of leaves in a binary tree T to be the order in which leaves are visited in a postorder traversal of T. Does reverse_leaves still work correctly, or does its implementation need to be modified to work with our new definition? If no changes are necessary, explain why using no more than a sentence or two. Otherwise, provide an alternate implementation of the reverse_leaves function called reverse_leaves_postorder to correspond to the new definition. Also answer the same question if the definition used "inorder" in place of "postorder". If you need to write a new function in this case, call it reverse_leaves_inorder.

Part 2 - Tree Traversals

Write a function check_valid(preorder, inorder, postorder) that takes as arguments the lists preorder, inorder, and postorder, and returns True if and only if there exists some binary tree T such that the lists represent preorder, inorder, and postorder traversals of T. The arguments are guaranteed to be 1 dimensional lists, possibly empty, in which each element is a integer (representing a node label). Also, you may assume that there are no duplicate elements in any of the lists. Beyond this information, you cannot make any assumptions about the arguments.

A naive solution is to figure out the tree's set of nodes based on the items in one of the arguments, generate all possible binary trees on this set of nodes, and perform preorder, inorder, and postorder traversals on each tree to see if the traversals correspond to the supplied arguments. If you find a tree whose traversals correspond to the supplied arguments, then you are done and return True. Otherwise, if you check each possible tree without finding one whose traversals match the arguments, you return False.

Although the naive solution described above will work, it is too inefficient. The number of binary trees on n nodes is roughly exponential in n, which means you have to check a lot of trees, even when the number of nodes is fairly small.

The solution that you come up with should be more efficient. In particular, it should take no more than O(n2) operations.

Part 3 - Gluing BSTs Together

In this part you will be "gluing" binary search trees together using a set of "glue nodes". A glue node is a single node with empty left and right subtrees. To use a glue node to glue two BSTs together, set one of the BSTs as the left subtree of the glue node, and the other BST as the right subtree of the glue node, so that the resulting tree is a valid binary search tree.

Very important: Glue nodes can only be used to glue together BSTs that contain at least two nodes. This means that you cannot glue a single BST to one side of a glue node to form a new BST, nor can you use a glue node to glue together two other "lone" glue nodes.

You are given a set of BSTs and a set of glue nodes. Your goal is to glue the BSTs together to form a single new BST containing the original BSTs and all the glue nodes.

Examples

Example 1. Suppose you are given the glue node 20 and the following BSTs:

     10        40
    /  \      /  \
   3    17   25   55

        20        
       /  \
      /    \
     10     40
    /  \    / \
   3    17 25  55

Example 2. Suppose you are given the glue nodes 20 and 60, and the following BSTs:

   40      10        80
  /  \    /  \      /  \
 25  55  3    17   75   90 

            60
           /   \
          /     \
         /       \
        20        80   
       /  \       / \
      /    \     /   \
     10     40  75   90
    /  \    / \
   3    17 25  55

Example 3. Suppose you are given the glue nodes 20 and 22, and the following BSTs:

     10        40       
    /  \      /  \     
   3    17   25   55  

Example 4. Suppose you are given the glue node 32 and the following BSTs:

     10        40       
    /  \      /  \     
   3    30   25   55  

Details

Write a function glue_bsts(bsts, glue_nodes) that takes as arguments a list of binary search trees (bsts), and a list of glue_nodes, and returns a new BST that is formed by gluing together the BSTs. If there is no way to create a new BST by gluing the individual BSTs together, then return None.

The bsts argument is a list containing instances of the BinarySearchTree class. Each BinarySearchTree instance in the bsts list is guaranteed to have at least two nodes. The glue_nodes argument is a list containing integers, representing labels of the glue nodes. If it's possible to glue together the BSTs, then the return value should be an instance of BinarySearchTree, representing the resulting binary search tree constructed after gluing together the BinarySearchTree instances in the bsts list. Otherwise, the return value should be None.

Your function should have time complexity O(n log n), where n is the total number of nodes across all binary search trees in the bsts argument plus all glue nodes.

Part 4 - Range searching

Your implementation should not visit more nodes in the tree than necessary. More precisely, the complexity of your method should be O(h + k), where h is the height of the BST, and k is the number of keys that fall within the specified range.

You may make any other additions necessary in the bst.py module, including adding methods to the TreeNode class, as you see fit. Do not remove or modify any existing method signatures, however.

What to Submit

1. Part 1 - submit your solution in the module part1.py. The answer to the question should be given in a docstring at the top of the module.
2. Part 2 - submit your solution in the module part2.py.
3. Part 3 - submit your solution in the module part3.py.
4. Part 4 - submit a modified copy of the bst.py module, containing your implementation of the search_range method.

NOTE:

• Submitting test code for this assignment is not necessary. However, you should still test your code thoroughly!
• Make sure you follow the instructions in each part of the assignment statement carefully. In particular, pay attention to how arguments and return values are defined. Any deviation from these instructions can potentially result in a large loss of correctness marks.
• You may create any additional helper functions/methods in parts 1 - 4 as you deem fit.

You need to submit electronically, and also submit a printed copy of your code. Be sure that you include your cdf id and student number in the hard copy that you hand in. The drop box for CSC148 is in BA2220.