Question

Problem 1:

Write a Java program for traversing a Binary Search Tree in following ways: (use any data structure, library functions) ---------- 20 points

i) Depth First Traversal: Inorder, LVR

ii) Depth First Traversal: Inorder, RVL

iii) Depth First Traversal: Preorder, VLR

iv) Depth First Traversal: Preorder, VRL

v) Depth First Traversal: Postorder, LRV

vi) Depth First Traversal: Postorder, RLV

No choice menu required.

Sample Input (taken from keyboard, single space separated nodes as found in a complete BFS: top-down, left to right traversal):

22 10 30 5 15 25 40 1 8

Sample Output (in console or in a file):

Depth First Traversal: Inorder, LVR -> 1 5 8 10 15 22 25 30 40

Depth First Traversal: Inorder, RVL -> 40 30 25 22 15 10 8 5 1

Depth First Traversal: Preorder, VLR -> 22 10 5 1 8 15 30 25 40

Depth First Traversal: Preorder, VRL -> 22 30 40 25 10 15 5 8 1

Depth First Traversal: Postorder, LRV -> 1 8 5 15 10 25 40 30 22

Depth First Traversal: Postorder, RLV -> 40 25 30 15 8 1 5 10 22

Upload one zipped file containing source code file (.java, .cpp or .py) and output screenshot files (in .jpeg, .bmp etc).

Answer 1

CODE:

public class BinarySearchTree {

class TreeNode {
public int key;
public TreeNode p;
public TreeNode left;
public TreeNode right;

public TreeNode() {
p = left = right = null;
}

public TreeNode(int k) {
key = k;
p = left = right = null;
}
}

public TreeNode root;

public BinarySearchTree() {
root = null;
}

public void insert(int k) {
TreeNode newNode = new TreeNode(k);
  
if(root == null) {
root = newNode;
} else {
TreeNode parent = root;
while(true) {
if(parent.key == k) {
return;
}
if(parent.key > k) {
if(parent.left == null) {
parent.left = newNode;
newNode.p = parent;
return;
} else {
parent = parent.left;
}
} else {
if(parent.right == null) {
parent.right = newNode;
newNode.p = parent;
return;
} else {
parent = parent.right;
}
}
}
}
}

private void inorderLVR(TreeNode t) {
if(t != null) {
inorderLVR(t.left);
System.out.print(t.key + " ");
inorderLVR(t.right);
}
}
private void inorderRVL(TreeNode t) {
if(t != null) {
inorderRVL(t.right);
System.out.print(t.key + " ");
inorderRVL(t.left);
}
}

private void preorderVLR(TreeNode t) {
if(t != null) {
System.out.print(t.key + " ");
preorderVLR(t.left);
preorderVLR(t.right);
}
}
private void preorderVRL(TreeNode t) {
if(t != null) {
System.out.print(t.key + " ");
preorderVRL(t.right);
preorderVRL(t.left);
}
}

private void postorderLRV(TreeNode t) {
if(t != null) {
postorderLRV(t.left);
postorderLRV(t.right);
System.out.print(t.key + " ");
}
}
private void postorderRLV(TreeNode t) {
if(t != null) {
postorderRLV(t.right);
postorderRLV(t.left);
System.out.print(t.key + " ");
}
}
  

/**
* @param args
*/
public static void main(String[] args) {
int[] array = {22, 10, 30, 5, 15, 25, 40, 1, 8};
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < array.length; i++)
bst.insert(array[i]);
  
bst.printReport();
}

private void printReport() {
inorderLVR(root);
System.out.println();
inorderRVL(root);
System.out.println();
preorderVLR(root);
System.out.println();
preorderVRL(root);
System.out.println();
postorderLRV(root);
System.out.println();
postorderRLV(root);
System.out.println();
}

}

OUTPUT: