THINK FIRST·CODE LATER

← All labs

Tree traversals without recursion

Problem

Recursion makes tree traversals three lines long, but each can also be written with an explicit stack — which is what the recursion does behind the scenes. Write StackTraversals:

  • inorder(root): go left as far as possible, pushing the nodes; pop one, visit it, and continue with its right subtree;
  • preorder(root): pop a node, visit it, push its right child then its left child;
  • postorder(root): the order "node, right, left", reversed;
  • a class InorderIterator implements Iterator<Integer> that delivers the keys in increasing order one at a time, keeping on its stack only the left branch still to be visited.

The first line of the input holds the keys to insert in a BST; the second, a number k. Print the three traversals and, with the iterator, the k smallest keys. For the input

50 30 70 20 40 60 80 35 45 65
4

the program prints

Inorder:   [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]
Preorder:  [50, 30, 20, 40, 35, 45, 70, 60, 65, 80]
Postorder: [20, 35, 45, 40, 30, 65, 60, 80, 70, 50]
The 4 smallest keys: 20 30 35 40
The iterator has more keys: true

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d12-9-data-1.txt

50 30 70 20 40 60 80 35 45 65
4
What your program must print for d12-9-data-1.txt
Inorder:   [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]
Preorder:  [50, 30, 20, 40, 35, 45, 70, 60, 65, 80]
Postorder: [20, 35, 45, 40, 30, 65, 60, 80, 70, 50]
The 4 smallest keys: 20 30 35 40
The iterator has more keys: true

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d12-9-data-1.txt

Windows PowerShell does not understand <:

Get-Content d12-9-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.