Question: Data Structures Make a main method to get output from this code in java class Node { int data; Node left; Node right; public Node(int
Data Structures
Make a main method to get output from this code in java
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
public String toString() {
return data + " ";
}
}
// Class BST to define the properties of the BST and methods to manipulate it
public class BST {
Node root;
public BST() {
root = null;
}
// Method to insert a node in the BST iteratively
public void insert(int x) {
Node n = new Node(x);
if (root == null) {
root = n;
return;
}
Node current = root;
Node parent = null;
while (true) {
parent = current;
if (x < current.data) {
current = current.left;
if (current == null) {
parent.left = n;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = n;
return;
}
}
}
}
// Method to insert a node in the BST recursively
private void insertR(Node start, int x) {
if (start == null) {
start = new Node(x);
return;
}
if (x < start.data) {
if (start.left == null) {
start.left = new Node(x);
} else {
insertR(start.left, x);
}
} else {
if (start.right == null) {
start.right = new Node(x);
} else {
insertR(start.right, x);
}
}
}
public void insertRec(int x) {
insertR(root, x);
}
// Method to find the minimum node in the BST
private int minimum(Node root) {
int min = root.data;
while (root.left != null) {
min = root.left.data;
root = root.left;
}
return min;
}
// Method to delete a node from the BST
private Node delete_Recursive(Node root, int key) {
if (root == null)
return root;
if (key < root.data) {
root.left = delete_Recursive(root.left, key);
} else if (key > root.data) {
root.right = delete_Recursive(root.right, key);
} else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.data = minimum(root.right);
root.right = delete_Recursive(root.right, root.data);
}
return root;
}
public void delete(int key) {
root = delete_Recursive(root, key);
}
// Method to traverse the BST in
public void inOrderTraversal(Node root) {
if (root != null) {
inOrderTraversal(root.left);
System.out.print(root + " ");
inOrderTraversal(root.right);
}
}
public void preOrderTraversal(Node root) {
if (root != null) {
System.out.print(root + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
}
public void postOrderTraversal(Node root) {
if (root != null) {
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root + " ");
}
}
// Method to check if the BST is empty
public boolean isEmpty() {
return (root == null);
}
// Method to find the height of the BST
private int height(Node root) {
if (root == null) {
return -1;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public int height() {
return height(root);
}
// Method to find the size of the BST
private int size(Node root) {
if (root == null) {
return 0;
}
return size(root.left) + 1 + size(root.right);
}
public int size() {
return size(root);
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help