CSCI 3333.3 Data Structures
Spring 2013
Suggested Solution to Homework #7

Exercises:

(1) [1 5 [[[[[] 9 [12 13 []]] 16 17] 18 []] 20 [22 37 [[] 47 90]]]]

(2)

After deleting 15: [[[7 10 [12 13 []]] 27 29] 30 [[] 60 90]]
After deleting 13: [[[7 10 12] 27 29] 30 [[] 60 90]]
After deleting 60: [[[7 10 12] 27 29] 30 90]
After deleting 29: [[[7 10 12] 27 []] 30 90]

(3) For example:

Algorithm RangeSearch(p: BST, low, high: integer);
Input:
    p: root of an integer binary search tree.
    [low, high]: the range of node values to be included the result.
Output:
    result: an integer array containing all integers in the BST
            with values in the range [low, high] in order.
    size: number of integers in the array result.

size <- 0;
result <- empty;
RangeSearchHelper(p, low, high, size, result);


Algorithm RangeSearchHelper(p: BST, low, high: integer, result: integer array, size: integer);
Input:
    p: root of an integer binary search tree.
    [low, high]: the range of key values to be included the result.
    result: an integer array that has been built so far.
    size: number of integers in the array result.  
Output:
    result: an integer array in which all integers in the BST p
           with values in the range [low, high] are added in order.
    size: number of integers in the array result.  

if p == null then
    return;
end if;

if p.value > low then
    RangeSearchHelper(p.left, low, high, result, size);
end if;

if low <= p.value and p.value <= high then
    result[size] <- p.value;
    size++;
end if;

if p.value < high then
    RangeSearchHelper(p.right, low, high, result, size);
end if;

Program:

(1) (10%) Copy the content of the immediate successor to the targeted node and delete the immediate successor (which has no left child).

(2) and (3):

In BinaryNode.java, add:

     // Print tree rooted at current node using inorder traversal with indentation
    public void printInOrder(int identLevel)
    {   if( left != null )
            left.printInOrder(identLevel+1);            // Left
        for (int i=0; i<identLevel; i++) System.out.print("    ");
        System.out.println(element);                   // Node
        if( right != null )
            right.printInOrder(identLevel+1);          // Right
    }
  
    // Print tree rooted at current node using inorder traversal
    // with element value within the range of [low, high].
    public static void printRange(BinaryNode t, Comparable low, Comparable high)
    {   if (t != null)
        {   if (low.compareTo(t.element) < 0)
                printRange(t.left, low, high);             // Left
            if ((low.compareTo(t.element) <= 0) && (high.compareTo(t.element) >= 0))
                System.out.println(t.element);            // Node
            if(high.compareTo(t.element) > 0)
                printRange(t.right, low, high);            // Right
        }
    }
  
    /**
     * Return the size of the binary tree rooted at t.
     */
    public static  int size( BinaryNode t )
    {
        if( t == null )
            return 0;
        else
            return 1 + size( t.left ) + size( t.right );
    }

   
 In the BinarySearchTree class, add:

    /**
     * Print BST with level indentation.
     */
    public void printBST()
    {
        if (root != null)
            root.printInOrder(0);
    }
    
    public int size( )
    {
        return BinaryNode.size( root );
    }
   
    public void printRange(Comparable low, Comparable high)
    {   if ( root != null )
            BinaryNode.printRange(root, low, high);
    }