Exercises - Binary Search Trees

  1. How many ways are there that can produce the worst case when we insert the elements $A, X, C, S, E, R, H$ into an empty binary search tree?

    Two -- alphabetical order and reverse alphabetical order

  2. How many binary tree shapes of $n$ nodes are there with height $n-1$?

    Two -- a binary tree with only left children and a binary tree with only right children.

  3. Given a BST in pre-order as $\{13, 5, 3, 2, 11, 7, 19, 23\}$, draw this BST and determine if this BST is the same as one described in post-order as $\{2, 3, 5, 7, 11, 23, 19, 13\}$.

    Remembering a BST must be in symmetric order, the BST initially described is given by

                     |
           +---------13--+
           |             |
        +--5-----+       19--+
        |        |           |
     +--3     +--11          23 
     |        |
     2        7
    

    In post-order, this tree would be described by $\{2,3,7,11,5,23,19,13\}$. So this is a different BST then the one described in post-order in the question.

  4. Complete the class BstChecker so that the isBst(Node root) method returns true if and only if the tree rooted at root is a binary search tree (i.e., a binary tree in symmetric order). You may assume all values in the nodes of the tree are unique positive integers.

    public class BstChecker {
        
        // INSERT VARIABLE DECLARATIONS HERE, AS DESIRED...
    
        private static class Node {
            int value;
            Node left;
            Node right;
            
            Node(int value) {
                this.value = value;
                left = null;
                right = null;
            }
        }
        
        public boolean isBst(Node root) {
    
            // INSERT CODE HERE...
        }
        
        // INSERT ADDITIONAL METHODS HERE, AS DESIRED...
    
        public static void main(String[] args) {
            Node r1 = new Node(13);
            r1.left = new Node(5);
            r1.right = new Node(19);
            r1.left.left = new Node(3);
            r1.left.left.left = new Node(2);
            r1.left.right = new Node(11);
            r1.left.right.left = new Node(7);
            r1.right.right = new Node(23);
            // Note, as defined above, r1 is a BST
            
            Node r2 = new Node(13);
            r2.left = new Node(5);
            r2.right = new Node(12);
            r2.left.left = new Node(6);
            r2.left.left.left = new Node(2);
            r2.left.right = new Node(11);
            r2.left.right.left = new Node(7);
            r2.right.right = new Node(23);
            // Note, as defined above, r2 is not a BST
    
            BstChecker bstChecker = new BstChecker();
            System.out.println(bstChecker.isBst(r1) ? "Is a BST" : "Not a BST");  
            System.out.println(bstChecker.isBst(r2) ? "Is a BST" : "Not a BST");  
        }
    }
    
  5. Complete the class BinaryTreeInOrderIterable so that it fully supports the Iterable interface with iteration producing the keys in order (i.e., from least to greatest, as dictated by their implementation of the Comparable interface).

    In doing so, you may add instance variables, as needed, to the anonymous class implementing the Iterator interface -- but do not add any additional methods to this anonymous inner class. Also refrain from adding any instance variables or methods to the outer class. As one final, but important limitation - accomplish this task without the use of recursion.

  6. To traverse a binary tree in level order means to start at the root, and then visit all nodes one node away from the root (starting with the left node, if not null); and then visit all nodes two nodes away from the root (again, left-most to right-most), as they exist; and then visit all nodes 3 nodes away from the root and so on...

    The following is a modified version of the binary search tree class developed elsewhere in these notes : BST.java. This new version includes an additional method named keysLevelOrder(), intended to return a queue of the keys of the binary search tree in level order.

    Complete this class by adding an appropriate body to this method. Do not add any instance variables or other methods to the class besides this one.

    You will need to include in your project the QueueArray class and the Queue interface it implements. These are, of course, necessary for the rest of the BST class to function, but you may find them very useful in implementing this new method as well.

    You can use the LevelOrderTest class to test your code. A sample run is shown below:

    $ java LevelOrderTest↵
    Enter a sequence of letters (all uppercase) to be inserted into a binary search tree:
    FGCEHBDA↵
    Level Order = FCGBEHAD
    
  7. Implement a Binary Search Tree (BST) based index for indexing/searching actors or movies in the IMDb dataset with the following characteristics:

    • Your implementation should allow the user to quickly find information associated with an actor, or a movie, based on the actor's or movie's name (e.g., "Arnold Schwarzenegger"), or a prefix of a name (e.g. "Arnold Schwarz*").

    • The search should be case insensitive (e.g., "arnold schwarz*" should also work.)

    • The search key is the short or simplified name of a movie or actor.

    • The information associated with the key should be of type MovieInfo.

    • The BST index should be implemented as a stand-alone class named BSTIndex, having at least the public methods listed below (you may add as many additional private helper methods as needed). You will need to define a Node class within the BSTIndex class that contains 3 fields: val (of MovieInfo type), and left & right references to the children nodes. As the key for comparison with other nodes (i.e., the short name) is already stored in the MovieInfo object, make a key() method in the node class to access this key rather than storing duplicate information.

      • public BSTIndex() : a constructor to initialize the BST. The data element should be an object of type MovieInfo as described above.

      • public MovieInfo findExact(String key) : returns the data MovieInfo element where the shortName matches the key exactly (although possibly with different capitalization).

      • public MovieInfo findPrefix (String prefix) : returns the data element MovieInfo where the shortName starts with the prefix (and possibly has different capitalization).

      • public void insert(MovieInfo data) : insert the given data element into the proper place in the BST structure.

    You can use the IndexTester class to test your BSTIndex class. When executed, this class creates an empty BSTIndex object (using the constructor of the BSTIndex class), reads the data from an input movie or actor file, builds a MovieInfo object for each row, and inserts this object into the BST index (using the insert() method of the BSTIndex class). At this point, the BST index is built for all the movie or actor entries in the file. It will then ask for a search string from user and search for the MovieInfo object associated with the name, testing the search functionality of the BSTIndex class (using its findExact or findPrefix methods).

    To test your code with the IndexTester class, you will need to provide it the name of a dataset file to index. You can use any of the following IMDB datasets to this end. Note the full data files (i.e., actors.txt and movies.txt) are relatively large. You will likely wish to use the smaller datasets (actors100K.txt and movies100K.txt) for debugging. All of the files are in the same format: one actor or movie per line, with fields: ID, shortName, fullName separated by a tab character ("\t"). Read the IndexTester to remind yourself how to read this data.

  8. Below are two sample runs -- one using the file actors.txt and the other using the file movies.txt:

    $ java IndexTester /Users/pauloser/Desktop/actors.txt↵
    Inserted 10000 records.
    Inserted 20000 records.
    Inserted 30000 records.
    Inserted 40000 records.
       .
       .
       .
    Inserted 1490000 records.
    Inserted 1500000 records.
    Index building complete. Inserted 1500502 records. Elapsed time = 17 seconds.
    Enter search string, end in a '*' for prefix search. q to quit
    Steve McQueen↵
    1185711 Steve McQueen McQueen, Steve (I)
    Jodie Fos*↵
    2010983 Jodie Foster Foster, Jodie
    
    $ java IndexTester /Users/pauloser/Desktop/movies.txt↵
    Inserted 10000 records.
    Inserted 20000 records.
    Inserted 30000 records.
    Inserted 40000 records.   
       .
       .
       .
    Inserted 560000 records.
    Inserted 570000 records.
    Index building complete. Inserted 577944 records. Elapsed time = 3 seconds.
    Enter search string, end in a '*' for prefix search. q to quit
    The Magnificent Seven↵
    44586 The Magnificent Seven Magnificent Seven, The
    The Silence of the*↵
    7205 The Silence of the Lambs The Silence of the Lambs