22C:030/115 Computer Science III

Fall 2001

Homework Assignment 4: Trees

DUE DATE: 11/9/01 (50 points)

1. Write a recursive function fringe(t) to print the data fields in the leaf nodes (i.e. nodes of degree 0) in the binary tree t from left to right. For example, given the tree below as input, your program should print "G E F".

   

2. Two binary trees have the same structure if all corresponding nodes in the two trees have the same structure (i.e. no children, only a left child, only a right child, or two children). Write recursive function to determine whether or not two binary trees have the same structure.

3. Write a function to determine if a binary tree is a binary search tree, i.e. if the order relations of the values in the tree satisfy the constraints of a binary search tree. To solve this problem you must determine whether or not every subtree t satisfies the requirement that all nodes in its left subtree have values less than t->data() and all values in its right subtree have values greater than t->data(). You can do this in a single traveral of the tree by constructing a helping or auxiliary function that creates a new interface for communicating information about subtrees back to parents during the traversal. The auxiliary function should pass back to the calling function 3 pieces of information about a tree: (1) Whether or not the tree is a binary search tree (true or false), (2) The minimum value in the tree, and (3) The maximum value in the tree. The auxiliary function should do a recursive traversal of the the tree. The function isBST(root_ptr) initiates the traversal by calling the auxiliary function. NOTE: Solutions that require multiple traversals will not receive full credit.

    template <class Item>
    bool isBST(BinaryTreeNode<Item>* root_ptr);
    // Precondition: root_ptr is a pointer to the root of a binary tree.
    // The tree may be empty or non-empty.
    // Postcondition: The return value is true if the binary tree is
    // a binary search tree and false otherwise.
 

4. Draw a picture of a binary search tree after each of following steps. Assume you start the operations with an empty tree.
   
   
• Insert 30
• Insert 15
• Insert 10
• Insert 40
• Insert 14
• Insert 20
• Insert 35
• Insert 38
• Insert 50
• Insert 18
• Insert 19
• Delete 35
• Delete 40
• Delete 15
• Delete 30
5. Consider the following priority queue implemented as a heap. Show the heap after the following operations. Draw the heap as a logical tree structure (as pictured below) .



• Insert(20)
• Insert(90)
• Serve()
• Serve()