For BST implementation language is Java Problem statement: For a binary tree, on

Question

For BST

implementation language is Java

Problem statement: For a binary tree, one of the traverse result is given as an input, your algorithm should create corresponding two other traverse results. For example, if in-order traverse is given, the pre-order and post-order should be created. Your report should include: a) pseudocode for your method, b) the program with comments, c) Big-0 analysis, d) your program's outputs for the following exact three inputs, in the same order: Pre-order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Post-order: ??? In-order: ??? In-order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Pre-order: ??? Post-order: ??? 3) Post-order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Pre-order: ??? In-order: ???

Explanation / Answer

package myProject;
import java.util.Scanner;
// Class BSTNode Definition
class BSTNode
{
BSTNode left, right;
int data;
// Default Constructor
public BSTNode()
{
left = null;
right = null;
data = 0;
}

// Parameterized Constructor
public BSTNode(int n)
{
left = null;
right = null;
data = n;
}

// Method sets left node
public void setLeft(BSTNode n)
{
left = n;
}

// Method sets right node
public void setRight(BSTNode n)
{
right = n;
}

// Method returns left node
public BSTNode getLeft()
{
return left;
}

// Method returns right node
public BSTNode getRight()
{
return right;
}

// Method sets data to node
public void setData(int d)
{
data = d;
}

// Method returns data from node
public int getData()
{
return data;
}
}//End of class

// Class BST Definition
class BST
{
private BSTNode root;

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

// Method inserts data to the tree
public void insert(int data)
{
root = insert(root, data);
}

// Method to insert data recursively
private BSTNode insert(BSTNode node, int data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}//End of method

   // Method counts and returns number of nodes
public int countNodes()
{
return countNodes(root);
}

// Method counts and returns number of nodes recursively
private int countNodes(BSTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}//End of method

// Method for In Order traversal
public void inorder()
{
inorder(root);
}

// Method for In Order traversal recursively
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}//End of method

// Method for Pre Order traversal
public void preorder()
{
preorder(root);
}

// Method for Pre Order traversal recursively
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());   
preorder(r.getRight());
}
}//End of method

// Method for Post Order traversal
public void postorder()
{
postorder(root);
}

// Method for Post Order traversal recursively
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getLeft());   
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}//End of method
}//End of class

// Driver Class BinarySearchTree Definition
public class BinarySearchTree
{
   //Main method definition
public static void main(String[] args)
{   
   //Scanner class object created to accept data
   Scanner scan = new Scanner(System.in);
  
   // BST class object Created
BST bst = new BST();

System.out.println("Binary Search Tree Test ");
char ch;
//Loops till user choice
do
{
System.out.println(" Binary Search Tree Operations ");
System.out.println("1. In Order ");
System.out.println("2. Pre Order");
System.out.println("3. Post Order");
// Accepts user choice for traversal
int choice = scan.nextInt();
// Accepts data to insert
System.out.println("Enter integer element to insert");
bst.insert( scan.nextInt() );
  
// Display tree with other than the selected order
switch (choice)
{
case 1 :
   System.out.print(" Pre order : ");
bst.preorder();
System.out.print(" Post order : ");
bst.postorder();
break;
case 2 :
   System.out.print(" In order : ");
bst.inorder();
System.out.print(" Post order : ");
bst.postorder();
case 3:
   System.out.print(" In order : ");
bst.inorder();
   System.out.print(" Pre order : ");
bst.preorder();        
default :
System.out.println("Wrong Entry ");
break;   
}//End of switch
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}//End of main method
}//End of class

Output:

Binary Search Tree Test

Binary Search Tree Operations

1. In Order
2. Pre Order
3. Post Order
1
Enter integer element to insert
23

Pre order : 23
Post order : 23
Do you want to continue (Type y or n)

y

Binary Search Tree Operations

1. In Order
2. Pre Order
3. Post Order
1
Enter integer element to insert
12

Pre order : 23 12
Post order : 12 23
Do you want to continue (Type y or n)

y

Binary Search Tree Operations

1. In Order
2. Pre Order
3. Post Order
1
Enter integer element to insert
11

Pre order : 23 12 11
Post order : 11 12 23
Do you want to continue (Type y or n)

y

Binary Search Tree Operations

1. In Order
2. Pre Order
3. Post Order
1
Enter integer element to insert
89

Pre order : 23 12 11 89
Post order : 11 12 89 23
Do you want to continue (Type y or n)

n

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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