This program makes a binary tree and manipulates it using many different methods. I just need help

Fantastic news! We've Found the answer you've been seeking!

Question:

This program makes a binary tree and manipulates it using many different methods. I just need help implementing a preorder or postorder traversal on my binary tree for my isSame() method to make sure both the trees are the same. Currently my method is only checking the inorder traversals, which doesn't satisfy the condition of inorder + preorder/postorder traversals to be the same if the trees are the same.

JAVA CLASS FILES (3)

StudentBinaryTree.java (1)

package exam3;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

public class StudentBinaryTree implements Iterable{
public static class Node {
private final UnfStudent studentInfo;
private Node left, right;
private final Node parent;

public Node(int nNumber, String name, double gpa, Node parent) {
studentInfo = new UnfStudent(nNumber, name, gpa);
this.parent = parent;
}

public String toString() {
return studentInfo.toString();
}
}

private Node root = null;

// 1
// inserts a new node using the path made up of 0s and 1s like we did in the class
public void insert(int nNumber, String name, double gpa, String path) {
// Complete; no two nodes can have the same UnfStudent
if (root == null) {
root = new Node(nNumber, name, gpa, null);
return;
}

Node currentNode = root;

for (int i = 0; i < path.length(); i++) {
if (path.charAt(i) == '0') {
if (currentNode.left == null) {
currentNode.left = new Node(nNumber, name, gpa, currentNode);
return;
} else
currentNode = currentNode.left;
} else {
if (currentNode.right == null) {
currentNode.right = new Node(nNumber, name, gpa, currentNode);
return;
} else
currentNode = currentNode.right;
}
}
}

// 2
// returns the binary path for the node that contains 'nNumber'; return null if such a node is not present
public String findPathEncodingOf(int nNumber) {
Node node = findNodeBynNumber(root, nNumber); // line 216
if (node == null) {
return null;
}

StringBuilder path = new StringBuilder();
while (node.parent != null) {
path.insert(0, node == node.parent.left ? '0' : '1');
node = node.parent;
}
return path.toString();
}

// 3
// returns the inorder traversal sequence, computed iteratively
public String inOrderNonRecursive() { // hint: use a stack; feel free to use java.util.Stack
// Complete
StringBuilder result = new StringBuilder();
Stack stack = new Stack<>();
Node current = root;

while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}

current = stack.pop();
result.append(current.studentInfo).append(" ");

current = current.right;
}

return result.toString();
}

// 4
// returns the inorder traversal sequence, computed recursively
public String inOrderRecursive() {
StringBuilder result = new StringBuilder();
inOrderRecursiveHelper(root, result);
return result.toString();
}

private void inOrderRecursiveHelper(Node node, StringBuilder result) {
if (node == null) {
return;
}

inOrderRecursiveHelper(node.left, result);
result.append(node.studentInfo).append(" ");
inOrderRecursiveHelper(node.right, result);
}

// 5
// returns the binary path from the node that contains 'nNumber' to the root
// return null if such a node is not present; hint: use the parent field
public String constructPathFromNodeToRoot(int nNumber) {
Node node = findNodeBynNumber(root, nNumber);
if (node == null) {
return null;
}

StringBuilder path = new StringBuilder();
while (node.parent != null) {
path.append(node == node.parent.left ? '1' : '0');
node = node.parent;
}

return path.reverse().toString();
}

// 6
// checks if the tree is also a BST
public boolean isBSTBasedOnnNumber() {
return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isBSTUtil(Node node, int min, int max) {
if (node == null) {
return true;
}

if (node.studentInfo.getnNumber() <= min || node.studentInfo.getnNumber() >= max) {
return false;
}

return isBSTUtil(node.left, min, node.studentInfo.getnNumber()) &&
isBSTUtil(node.right, node.studentInfo.getnNumber(), max);
}

// 7
// checks if the tree is also a min-heap
public boolean isHeapBasedOnnNumber() {
return isHeapUtil(root);
}

private boolean isHeapUtil(Node node) {
if (node == null)
return true;

// Check if the left child's nNumber is smaller than the current node's nNumber
if (node.left != null && node.left.studentInfo.getnNumber() < node.studentInfo.getnNumber())
return false;

// Check if the right child's nNumber is smaller than the current node's nNumber
if (node.right != null && node.right.studentInfo.getnNumber() < node.studentInfo.getnNumber())
return false;

// Recursively check the left and right subtrees
return isHeapUtil(node.left) && isHeapUtil(node.right);
}

// 8
// counts the number of students whose gpa is > 'g'
public int numberOfStudentsWhoseGPAisGreaterThan(double g) {
return countStudentsWithGPA(root, g);
}

private int countStudentsWithGPA(Node node, double g) {
if (node == null)
return 0;

int count = 0;

if (node.studentInfo.getGPA() > g)
count++;

count += countStudentsWithGPA(node.left, g);
count += countStudentsWithGPA(node.right, g);

return count;
}

// 9
// returns the name of the student whose nNumber is known
public String findTheNameOf(int nNumber) {
Node node = findNodeBynNumber(root, nNumber);
return node == null ? null : node.studentInfo.getName();
}

private Node findNodeBynNumber(Node node, int nNumber) {
if (node == null) {
return null;
}

if (node.studentInfo.getnNumber() == nNumber) {
return node;
}

Node leftResult = findNodeBynNumber(node.left, nNumber);
Node rightResult = findNodeBynNumber(node.right, nNumber);

return leftResult != null ? leftResult : rightResult;
}

// 10
// returns the number of nodes having 2 children
public int countNumberofNodesHaving2children() {
return countNodesWithTwoChildren(root);
}

// recursive helper method to count nodes with 2 children
private int countNodesWithTwoChildren(Node node) {
if (node == null) {
return 0;
}

int count = 0;
if (node.left != null && node.right != null) {
count++; // increment count if the node has both left and right children
}

count += countNodesWithTwoChildren(node.left);
count += countNodesWithTwoChildren(node.right);

return count;
}

// 11
// returns the number of leaves
public int countNumberofLeaves() {
return countLeaves(root);
}

// recursive helper method to count leaves
private int countLeaves(Node node) {
if (node == null) {
return 0;
}

if (node.left == null && node.right == null) {
return 1; // increment count if the node is a leaf (no children)
}

int count = 0;
count += countLeaves(node.left);
count += countLeaves(node.right);

return count;
}

// 12
// checks if this current tree is same as the given tree 'B'
// 2 binary trees are same if their inorder traversal sequence + preorder/postorder sequences are same
public boolean isSame(StudentBinaryTree B){
String currentInOrder = inOrderRecursive(); // Get the inorder traversal of the current tree
String BInOrder = B.inOrderRecursive(); // Get the inorder traversal of tree B

return currentInOrder.equals(BInOrder); // Compare the inorder traversals
}

// 13
// returns the nNumber stored in the inorder successor; null it does not exist
public UnfStudent inOrderSuccessorOf(int nNumber){
Node node = findNodeBynNumber(root, nNumber); // Find the node with the given nNumber

if (node == null || node.right == null) {
return null; // Return null if the node is not found, or it doesn't have a right child
}

// Find the leftmost node in the right subtree, which will be the inorder successor
Node successor = node.right;
while (successor.left != null) {
successor = successor.left;
}

return successor.studentInfo;
}

// iterator method
// Complete the iterator for this class
public Iterator iterator() {
return new TreeIterator();
}

public class TreeIterator implements Iterator {
private final Stack stack;

public TreeIterator() {
stack = new Stack<>();
pushLeftNodes(root);
}

private void pushLeftNodes(Node node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}

public boolean hasNext() {
return !stack.isEmpty();
}

public UnfStudent next() {
if (!hasNext()) {
throw new NoSuchElementException();
}

Node node = stack.pop();
pushLeftNodes(node.right);
return node.studentInfo;
}
}
}

TestStudentBinaryTree.java (2)

package exam3;

public class TestStudentBinaryTree {
public static void main(String[] args){
StudentBinaryTree B = new StudentBinaryTree();
B.insert(123, "Alice Wonder", 2.3, "root");
B.insert(456, "Bob Schmidt", 2.4, "1");
B.insert(457, "Leon Turner", 2.7, "0");
B.insert(789, "Cameron Ruble", 2.5, "01");
B.insert(910, "Dalton Wilken", 2.6, "11");

StudentBinaryTree A = new StudentBinaryTree();
A.insert(123, "Alice Wonder", 2.3, "root");
A.insert(456, "Bob Schmidt", 2.4, "1");
A.insert(457, "Leon Turner", 2.7, "0");
A.insert(789, "Cameron Ruble", 2.5, "01");
A.insert(910, "Dalton Wilken", 2.6, "11");

// 1 - insert()
System.out.println("Inorder traversal: ");
for(UnfStudent student : B)
System.out.println(student);

// 2 - findPathEncodingOf()
System.out.println("Path Encoding: ");
System.out.println(B.findPathEncodingOf(789));

// 3 - inOrderNonRecursive()
System.out.println("Inorder Non-Recursive: ");
System.out.println(B.inOrderNonRecursive());

// 4 - inOrderRecursive()
System.out.println("Inorder Recursive: ");
System.out.println(B.inOrderRecursive());

// 5 - constructPathFromNodeToRoot()
System.out.println("Node to Root Path: ");
System.out.println(B.constructPathFromNodeToRoot(789));

// 6 - isBSTBasedOnnNumber()
System.out.println("Is BST Based on nNumber: ");
System.out.println(B.isBSTBasedOnnNumber());

// 7 - isHeapBasedOnnNumber()
System.out.println("Is Heap Based on nNumber: ");
System.out.println(B.isHeapBasedOnnNumber());

// 8 - numberOfStudentsWhoseGPAisGreaterThan()
System.out.println("Number of Students w/> GPA: ");
System.out.println(B.numberOfStudentsWhoseGPAisGreaterThan(2.3));

// 9 - findTheNameOf()
System.out.println("Find Name of nNumber: ");
System.out.println(B.findTheNameOf(123));

// 10 - countNumberofNodesHaving2children()
System.out.println("Nodes w/2 Children: ");
System.out.println(B.countNumberofNodesHaving2children());

// 11 - countNumberofLeaves()
System.out.println("Number of Leaves in Tree: ");
System.out.println(B.countNumberofLeaves());

// 12 - isSame()
System.out.println("Is same: ");
System.out.println(B.isSame(A));

// 13 - inOrderSuccessorOf()
System.out.println("In-order Successor of: ");
System.out.println(B.inOrderSuccessorOf(910));
}
}

UnfStudent.java (3)

package exam3; // do not delete

public class UnfStudent {
private int nNumber;
private String name;
private double gpa;

public UnfStudent(int nNumber, String name, double gpa){
this.nNumber = nNumber;
this.name = name;
this.gpa = gpa;
}

public int getnNumber() { return nNumber; }
public void setnNumber(int n) { nNumber = n; }
public String getName() { return name; }
public void setName(String s) { name = s; }
public double getGPA() { return gpa; }
public void setGpa(double g) { gpa = g; }

public String toString() {
return "<" + nNumber + ", " + name + "> ";
}
}