BST Dictionary Traversals - 10 Course Points

The purpose of this assignment is to learn how to implement pre-order, post-order, in-order, and level-order traversals for a BST.

You can download and submit the project files via Autolab.

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.

See this video on how to import the project into VSCode and how to submit into Autolab.

The assignment has one component:

  • Coding (10 points) submitted through Autolab. 

Overview

Binary search trees are recursive structures that start off at a node and then branch off into different levels. They store items using keys for comparison — you can’t have duplicate keys in a BST. 

Since there are different ways we can branch off to in a BST, we can’t simply do a linear traversal like we have with arrays and linked lists. We’ll have to use algorithms that traverse deeper into the tree to find all nodes. In this lab, you’ll work with four key traversal methods: inorder traversal, preorder traversal, postorder traversal, and level-order traversal. 

Specifically, you’ll store words and definitions to implement a dictionary using a BST. Words will serve as the keys, and you’ll use lexicographic order (as .compareTo does) to determine orders and comparisons. For instance, “Data” should be to the left of “Structure” if “Structure” is the root. 

Word.java is a class that stores words and definitions, as strings. In the key value pair, the word is the key and the definition is the value. The BSTNodes will contain Word objects as their data. Meanwhile, BSTDictionary.java is where you will write your solution code. 

Working with BSTNode<> objects

For assignments/labs in CS112, we will use a cs112.jar file containing useful classes. This includes the BSTNode<> class, which implements a binary tree node. You’ve previously worked with the LLNode<> class to create linked lists. Many aspects of the BSTNode are similar:

  • The BSTNode class takes in a generic type, which means it can store any type of data. In this assignment you will be working with nodes that have Word objects as their data – to have nodes with Word data we can use BSTNode<Word>

  • Making a node: BSTNode<T> newNode = new BSTNode(data) — replace T with a type

    • Note that the data must be passed in for the constructor, and the data a node holds can not be changed later (aka it is immutable). The data may not be null.

  • Methods: 

    • getLeft() – returns the left child of the node
    • setLeft(BSTNode left) – sets the left child of the node
    • getRight() – returns the right child of the node
    • setRight(BSTNode right) – sets the right child of the node
    • getData() returns the data object a node holds

Directions

  • DO NOT add new import statements.
  • DO NOT add any new class attributes
  • DO NOT change any of the method’s signatures.
  • DO NOT modify the given constructor.

To complete this lab, you must implement the four traversal methods below. The method signatures are already given, do not modify these or add any new ones.

addWord [PROVIDED]

This method is provided for you, and inserts a node containing a word and definition into the BST rooted at the instance variable “root”. It updates that instance variable if the tree is empty; otherwise it follows BST insertion rules to insert a node in its proper position.

  • Words with names greater than a node’s name are stored to the right of the node, otherwise they are stored to the left. We compare based on word names: we use the compareTo() method to determine where to place words lexicographically (ie. comparing strings).

preOrder()

Preorder traversal immediately visits a node, and then traverses recursively through its left and right subtrees (in that order). 

You’ll create an ArrayList of all nodes, using preorder traversal for ordering. Add the node to the ArrayList, and then recursively traverse the node’s left and right subtrees. 

After the traversal is complete, return the ArrayList. 

Be careful with the order in which you insert nodes for testing — inserting in ascending order will result in a different tree. The driver and the image below insert BST, Queue, Circular Linked List, Stack, Linked List, and Union Find in that order.

postOrder()

Postorder traversal recursively visits a node only after all of its left and right children have been visited. In other words, for any node postorder traversal calls itself on the left child first, then the right child, and finally visits the node itself. 
 
You will create an ArrayList of all nodes using postorder traversal to determine order. Once the left and right children have been visited recursively, add the node to your ArrayList. 
 
At the end of the method, once your recursive traversal is done, return the ArrayList. 
 

Here’s an example of the order in which postorder traversal visits/prints nodes:

inOrder()

Inorder traversal will give you all keys in ascending order. For any node, it recursively traverses a node’s left subtree, then visits itself, and then recursively traverses a node’s right subtree.

You’ll also create an ArrayList of all nodes, using inorder traversal for ordering. Once the left subtree is visited, add the node to the ArrayList and then recursively traverse the right subtree. 

At the end of the method, return the ArrayList. 

levelOrder()

Level-order traversal goes through the tree for each level. Rather than the previous methods where the traversals were recursive, we add nodes to a queue and traverse them in the levels they appear in. You’ll still add each node as it’s visited to a resulting ArrayList, like the previous tasks.
 
Algorithm for level-order traversal of the BST:
  • Use the provided Queue class to initialize a queue of BSTNodes. 
    • Queue< BSTNode<Word>> queue = new Queue<>(); initializes the queue.
    • Then, you may use:
      • queue.enqueue(item) enqueues the parameter item into a queue.
      • queue.dequeue() dequeues an item as discussed in class.
      • queue.isEmpty() checks if the queue is empty.
  • Add the BST’s root to the Queue.
  • While the queue is not empty:
    • Dequeue a node. 
    • Add the node to the ArrayList.  
    • Enqueue the node’s children.

Here is an example for you to visualize:

  • The queue starts as empty. Start by enqueuing the root (at position 1).
  • Dequeue the node at position 1, visit it, and enqueue its left and right children (positions 2 and 3).
  • Repeat the same procedure on all other nodes until the queue is empty:
    • Dequeue the node at position 2, visit it, and enqueue its children.
    • Dequeue the node at position 3, visit it, and enqueue its children.
    • Lastly, dequeue and visit positions 4 and 5. They are leaves.
 
 

Driver

Once you implement your code, you can run the Driver.java file and interact with the driver. It’ll show three tabs: “Dictionary”, “Traversals”, and “BST Display”.

You can add words and definitions, and see all words added in the Dictionary tab. The traversals tab will show you the results of all traversals, while the BST Display tab will allow you to visualize the BST. 

Here’s an example of how the driver works:

The Dictionary tab shows all words and definitions. It CALLS the inorder method in order to give you the words and definitions, so if you haven’t implemented it or if it’s incorrect it won’t work. 

You don’t have to input full definitions for each word each time you test – remember that our traversals don’t use values, only keys (word names). The traversals below assume a tree in which BST, Queue, Circular Linked List, Stack, Linked List, and Union Find are inserted in that order.

Traversals will show you the result of all tree traversals. You might have to resize or scroll to see all items.

Lastly, BST Display will allow you to see the BST generated by inserting all nodes. You might have to resize or scroll to see all – use the scrollbars, don’t zoom. 

Writing JUnit Tests

You do not have to submit this, this is for you to test your own code.

In the main project folder, there exists a “test” folder next to the “src” folder. This contains a JUnit test class, which can run and test pieces of your code. To compile and run these tests, you must install the Test Runner extension. See the Programming FAQ for more info on VScode extensions.

You must fill the traversal tests in for them to work. Once you do, remove the fail() statements at the bottom and run. 

You are provided with a premade JUnit test class. You can finish writing the test methods, by using JUnit test methods (assertTrue(), assertFalse(), assertEquals()) in order to test your code.

If you’d like to use unit tests, you can:

  • Instantiate a new BSTDictionary object.
  • Call .addWord on any words you’d like to insert (remember that BSTs follow specific ordering rules). 
  • Create an array or ArrayList that stores the expected order of nodes as a result of the traversal. Make sure this is correct!
  • Call the traversal.
  • Compare each element against your expected and actual lists to see if there are any differences. 

Tests not running? 

First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. Remember that you must fill in the tests yourself.

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download BSTDictionaryTraversal.zip from Autolab Attachments.

  2. Unzip the file by double clicking.

  3. Open VSCode

    • Import the folder to a workspace through File > Open Folder

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.

  • How to debug your code

  • You can hit the triangle “Run Java” button at the top of the Driver.java class, or right click on Driver.java and select “Run Java”

NOTE: if you have BSTDictionaryTraversal (2) -> BSTDictionaryTraversal or CS112 -> BSTDictionaryTraversal in VS Code, open the INNERMOST BSTDictionaryTraversal through File -> Open Folder.

Before submission

REMOVE all print statements you have written in BSTDictionary.java 

Collaboration policy. Read our collaboration policy on the course syllabus.

Submitting the assignment. Submit BSTDictionary.java separately via the web submission system called Autolab. To do this, go to Autolab and find the correct assignment and submit your Java file.

  

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors and Instructional Assistants office hours here
  • In addition there is the Coding and Social Lounge (CSL) , a community space staffed with student community managers which are undergraduate students further along the CS major to answer questions.

By Colin Sullivan

White RU Logo

Rutgers is an equal access/equal opportunity institution. Individuals with disabilities are encouraged to direct suggestions, comments, or complaints concerning any
accessibility issues with Rutgers websites to accessibility@rutgers.edu or complete the Report Accessibility Barrier / Provide Feedback form.

Copyright © , Rutgers, The State University of New Jersey. All rights reserved. Contact webmaster