Use Java programming language to implement binary search tree (BST) with inserti

Question

Use Java programming language to implement binary search tree (BST) with insertion and pre-order, post-order and in-order traversal operations. The program must read a list of strings from an input file and insert them into the binary search tree. Then it must traverse the tree in pre-order, in-order and post-order manner and print the data in the tree on the screen.

Input file:

The program has one input file called "data.txt" that contains a string on each line. There is no repetitive string in the file. Below is a sample input file:

New York

Cairo

Toronto

Barcelona

London

Paris

Rome

Athens

Venice

Output:

The program must read each string from the input file, and inserts it into a binary search tree, then it prints the contents of the tree while traversing in three ways: pre-order, in-order and post-order.

Explanation / Answer

BST.java

import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class BST {

/* Class containing left and right child of current node and key value*/
class Node {
String key;
Node left, right;

public Node(String item) {
key = item;
left = right = null;
}
}

// Root of BST
Node root;

// Constructor
BST() {
root = null;
}

// This method mainly calls insertRec()
void insert(String key) {
root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
Node insertRec(Node root, String key) {

/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}

/* Otherwise, recur down the tree */
if (key.compareTo(root.key) < 0)
root.left = insertRec(root.left, key);
else if (key.compareTo(root.key) > 0)
root.right = insertRec(root.right, key);

/* return the (unchanged) node */
return root;
}

// This method mainly calls InorderRec()
void inorder() {
System.out.println("Inorder:");
inorderRec(root);
System.out.println();
}

// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
  
  
// This method mainly calls preorderRec()
void preorder() {
System.out.println("Preorder:");
preorderRec(root);
System.out.println();
}

// A utility function to do preorder traversal of BST
void preorderRec(Node root) {
if (root != null) {
System.out.print(root.key + " ");
inorderRec(root.left);
inorderRec(root.right);
}
}

// This method mainly calls postorderRec()
void postorder() {
System.out.println("Postorder:");
postorderRec(root);
System.out.println();
}

// A utility function to do postorder traversal of BST
void postorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
inorderRec(root.right);
System.out.print(root.key + " ");
}
}
// Driver Program to test above functions
public static void main(String[] args) throws IOException {
  
FileReader filereader = new FileReader("data.txt");
Scanner sc = new Scanner(filereader);
  
BST tree = new BST();

while(sc.hasNext())
{
tree.insert(sc.next());
}
  
// print inorder traversal of the BST
tree.inorder();
  
// print preorder traversal of the BST
tree.preorder();
  
//print postorder traversal of the BST
tree.postorder();
  
sc.close();
filereader.close();
}
}

Sample output

Inorder:
Athens Barcelona Cairo London New Paris Rome Toronto Venice York
Preorder:
New Athens Barcelona Cairo London Paris Rome Toronto Venice York
Postorder:
Athens Barcelona Cairo London Paris Rome Toronto Venice York New

Please rate positively if this answered your query.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.