Skip to Main Content

Data Structures

Computer Science Department

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.

Start your assignment early! You need time to understand the assignment and to answer the many questions that will arise as you read the description and the code provided.

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.

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. 

WordNode.java is a class that stores words and definitions, as strings. This class also stores left and right children. You’ll use getters and setters in order to access the words, definitions, and children. Meanwhile, BSTDictionary.java is where you will write your solution code. 

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. 
 
Hint: Create a helper method to traverse recursively and add to the ArrayList given a node – you can refer to the traversal code from class. The method signature provided doesn’t take in a node or an ArrayList, so you’ll have to create a new helper method. 

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 WordNodes. 
    • Queue< WordNode> 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. 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 BSTDictionary.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.
  • Use the run option in VS Code to run this program – right click BSTDictionary.java and select Run Java. It’s harder to use the terminal as the commands differ based on OS. 
  • NOTE: if you have BSTDictionaryTraversal (2) -> BSTDictionaryTraversal or CS112 -> BSTDictionaryTraversal in VS Code, open the INNERMOST BSTDictionaryTraversal through File -> Open Folder.
To run JUnit tests: right click test/DictionaryTest.java in VS Code and select Run Tests. 

Before submission

COMMENT all printing statements you have written from BSTDictionary.java 

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit BSTDictionary.java separately via the web submission system called Autolab. To do this, click the Labs and Assignments link from the course website; click the Submit link for that assignment.

Getting help

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

  • Find instructors office hours here
  • Find tutors office hours on Canvas -> Tutoring
  • Find head TAs office hours here
  • In addition to office hours we have the Coding and Social Lounge (CSL) , a community space staffed with community managers who are undergraduate students further along the CS major to answer questions.

By Colin Sullivan