As the title suggests, I am currently trying to construct a binary tree wherein user inputs are inserted in in-level order. Almost all of the tutorials and implementations in Java that I've read uses a sorted method of insertion.
I've tried gfg's method, but it uses queues, which resulted me being graded 0.
gfg method:
void addData(int data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
} else {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (true) {
Node node = queue.remove();
if (node.left != null && node.right != null) {
queue.add(node.left);
queue.add(node.right);
}
else {
if (node.left == null) {
node.left = newNode;
queue.add(node.left);
} else {
node.right = newNode;
queue.add(node.right);
}
break;
}
}
}
}
Input: 1 2 3 4 5 6 7 Output (In-order): 4 2 5 1 6 3 7 (Correct, but as mentioned it uses queues)
The insertion that I understand w/o queues (but this one sorts user input):
private Node insertNode(Node current, int data) {
if (current == null) {
return new Node(data);
}
if (data < current.data) {
current.left = insertNode(current.left, data);
}
else if (data > current.data) {
current.right = insertNode(current.right, data);
}
else {
return current;
}
return current;
}
public void addNode(int data) {
root = insertNode(root, data);
}
Input: 1 2 3 4 5 6 7 Output (In-Order): 1 2 3 4 5 6 7
To note, yes, I've also tried to implement gfg's method to what I understand. But I personally cannot make it make sense? I'm really stuck.
Edit: The whole code:
import java.util.Scanner;
public class BinaryTree {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
right = left = null;
}
}
public static class treeBinary {
Node root;
treeBinary() {
root = null;
}
private Node insertNode(Node current, int data) {
if (current == null) {
return new Node(data);
}
if (data < current.data) {
current.left = insertNode(current.left, data);
}
else if (data > current.data) {
current.right = insertNode(current.right, data);
}
else {
return current;
}
return current;
}
public void addNode(int data) {
root = insertNode(root, data);
}
public void inorderPrint(Node node) {
if (node != null) {
inorderPrint(node.left);
System.out.print(" " + node.data);
inorderPrint(node.right);
}
}
void inorderPrint() {
inorderPrint(root);
}
public void preorderPrint(Node node) {
if (node != null) {
System.out.print(" " + node.data);
preorderPrint(node.left);
preorderPrint(node.right);
}
}
void preorderPrint() {
preorderPrint(root);
}
public void postorderPrint(Node node) {
if (node != null) {
postorderPrint(node.left);
postorderPrint(node.right);
System.out.print(" " + node.data);
}
}
void postorderPrint() {
postorderPrint(root);
}
}
public static void main(String[] args) {
Scanner inputUser = new Scanner(System.in);
treeBinary userBT = new treeBinary();
boolean userChoice = false;
int count = 0;
mainMenu:
do {
System.out.println("\n\n\n1 - Add Data");
System.out.println("2 - Print (In-Order)");
System.out.println("3 - Print (Pre-Order");
System.out.println("4 - Print (Post-Order)");
System.out.println("5 - Exit");
System.out.print("Enter your choice: ");
switch (inputUser.nextInt()) {
case 1:
System.out.print("How many will you input? ");
int x = inputUser.nextInt();
for (int i = 0; i < x; i++) {
System.out.print("Input Data " + (count+1) + ": ");
userBT.addNode(inputUser.nextInt());
count++;
}
break;
case 2:
System.out.println("The Tree in In-Order: ");
userBT.inorderPrint();
break;
case 3:
System.out.println("The Tree in Pre-Order: ");
userBT.preorderPrint();
break;
case 4:
System.out.println("The Tree in Post-Order: ");
userBT.postorderPrint();
break;
case 5:
break mainMenu;
default:
System.out.println("Invalid Input!");
}
}
while (!userChoice);
}
}
After days and hours of trying and reading. I applied the idea of balancing the tree from the user's inputs instead of inserting in comparison with the previous input data. Personally, I don't know if this is what the professor is looking for, but I'll try and try. Thanks @trincot
Here is what I've came up with, just a mishmash of everything that I've read and watched, nothing original:
public static class treeBinary {
boolean checkBal(int countSide) {
countSide = countSide + 1;
while (countSide % 2 == 0) {
countSide = countSide / 2;
}
if (countSide == 1) {
return true;
}
else {
return false;
}
}
Node insertData(Node root, int data) {
if (root == null) {
Node newNode = new Node(data);
return newNode;
}
if (root.rightSide == root.leftSide) {
root.left = insertData(root.left, data);
root.leftSide++;
}
else if (root.rightSide < root.leftSide) {
if (checkBal(root.leftSide)) {
root.right = insertData(root.right, data);
root.rightSide++;
}
else {
root.left = insertData(root.left, data);
root.leftSide++;
}
}
return root;
}
void inorderPrint(Node node) {
if (node != null) {
inorderPrint(node.left);
System.out.print(node.data + " ");
inorderPrint(node.right);
}
}
}
I'll try to refine even more to the extent of my knowledge as a learning student.