Input string to binary tree inorder traversal

I am creating a program that accepts the bracket notation of a binary tree, and then provides various functions such as inorder traversal.

For the sake of this example: Input is G(Y(u)(5))(2(t)).

When traversing through the tree, my code only returns Y G u , but it should return u Y 5 G 2 t.

My main method provides a GUI for the user to enter the binary tree string. I have a separate class that constructs the binary tree and contains a private class that constructs each node.

I have reviewed my code, but can't quite figure out what the issue is.
I have checked out Geeks for Geeks as well as YouTube videos, but I am having issues grasping the concept.

public class BinaryTree {
Node root;
Node parent;
Character c;
String r;
String tree;
public BinaryTree(String tree) { // constructor
this.tree = tree;
}
public Node strToTree(String tree) {
Queue<String> queue = new LinkedList<>(); 
Stack<String> stack = new Stack<>(); 
String[] a = tree.split(""); 
int i = 0;
while (i < tree.length()) { // holds string's chars
queue.add(a[i]);
i = i + 1;
}
while (!queue.isEmpty()) { 
String b = queue.remove();
if (!b.equals("(")) {
stack.push(b); // stores closed brackets, number, & letters
if (b.equals(")") & !stack.isEmpty()) {
stack.pop(); // parenthesis
String e = stack.pop(); // character
String f = stack.lastElement();
c = e.charAt(0);
char g = f.charAt(0);
root = new Node(c);
parent = new Node(g);
if (parent.left == null) {
parent.left = root;
parent = parent.left;
} else
parent.right = root;
}
}
}
return root;
}
public void inOrderTraverse(String tree) {
Node root = new Node(tree.charAt(0));
Node left = new Node(tree.charAt(2));
Node right = new Node(tree.charAt(4));
getString(tree);
root.inOrderTraverse(left);
root.inOrderTraverse(root);
root.inOrderTraverse(right);
root.inOrderTraverse(left.left); // testing case
}
static class Node {
char data;
Node left;
Node right;
Node root;
private Node(char data) { // constructor
this.data = data;
left = null;
right = null;
}
public void inOrderTraverse(Node root) {
if (root == null)
return;
/* first recur on left child */
inOrderTraverse(root.left);
// (root.left);
/* then print the data of node */
System.out.print(root.data + " ");
/* now recur on right child */
inOrderTraverse(root.right);// root.right);
}
}
}

The logic in strToTree is not correct. Some of the issues:

• Every time a ")" is processed the root variable is overwritten with a new node -- so losing whatever was there before.

• It cannot be right that you would have to create two nodes whenever a ")" is encountered.

• stack.lastElement() may be executed on an empty stack...

• By setting parent.right = root; you admit that root has a parent, so then return root is not returning the root.

• if (parent.left == null) { might not be the right way to detect that the left child has to receive the new child. Consider that an input might have A()(C) to indicate that "A" has no left child, but does have a right child (C). You would need to somehow register that () was the input for the left child, keeping it null, while the next information would serve for a right child.

• ...

Some other remarks:

• The Node class should not have a root member. Only the BinaryTree class should have that.

• The BinaryTree class should not need parent (a tree has no parent), c (that should just be a local variable), r (?), nor even tree (as that is string input that should immediately be converted to the tree itself -- there is no need to persist that). So the only property a tree needs is its root.

• strToTree should better return a new BinaryTree instance instead of a Node. So it should be a static method, or even better, a constructor for the class.

• I don't see what you intended to do with the inOrderTraverse method you have on the BinaryTree class. It should just call the method with the same name on the Node class.

• The inOrderTraverse method on the Node class should be static (it doesn't use the current node this).

• Using a Queue is overkill. You can just iterate the characters of the input string.

• To keep track of whether the next token in the input string is about a left or a right child, you could also stack a boolean for each node that is on the stack. You could for instance have a stack of pairs <Node, Boolean>, or just two stacks that operate in tandem.

Here is an overhaul of your code:

public class BinaryTree {
Node root;
public BinaryTree(String input) {
root = null;
Stack<Node> stack = new Stack<>();
Stack<Boolean> sidestack = new Stack<>(); 
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
if (ch == ')') {
if (input.charAt(i-1) != '(') { // Exclude empty node 
stack.pop(); // This node has no more children to add
sidestack.pop();
}
} else if (ch != '(') {
Node node = new Node(ch);
if (stack.isEmpty()) {
root = node; 
} else {
boolean side = sidestack.peek();
if (side) {
stack.peek().right = node;
} else {
stack.peek().left = node;
}
sidestack.pop();
sidestack.push(!side); // Toggle child
}
stack.push(node);
sidestack.push(false);
}
}
}
public void inOrderTraverse() {
Node.inOrderTraverse(root);
}
static class Node {
char data;
Node left;
Node right;
private Node(char data) { // constructor
this.data = data;
left = null;
right = null;
}
static public void inOrderTraverse(Node root) {
if (root == null)
return;
inOrderTraverse(root.left);
System.out.print(root.data + " ");
inOrderTraverse(root.right);
}
}
// Demo
public static void main(String[] args) {
String input = "G(Y(u)(5))(2()(t))";
BinaryTree tree = new BinaryTree(input);
tree.inOrderTraverse();
}
}