I need help writing the java program that uses recursion to traverse through a b
ID: 3813190 • Letter: I
Question
I need help writing the java program that uses recursion to traverse through a binary tree. The only characters in the input tree are (,), and a-z.
This is the input tree -> empty-tree | (alpha tree tree) ecursive case empty-tree -> () \base case (a(b()())(c(d()())()))
a = root node b = left child empty left and right children c = right child d = left child empty left and right children empty right child
Output should be:
a b
a c d
What i have so far.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Lab6 {
public static ArrayList<String> paths = new ArrayList<>();
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter a valid tree: (a(b()())(c()()))");
String tree = s.next();
processTree(tree, "");
//print all items inside of paths ArrayList
}
//Recursive tree processing method
public static void processTree(String tree, String path)
{
String[] split = splitTree(tree);//only run if tree is not empty
System.out.println(Arrays.toString(split));
//when you reach the end of a path, add it to the ArrayList
}
//helper method to break up non-empty trees
public static String[] splitTree(String tree)
{
//expected tree format
//(node tree tree)
//0 1 2-x x-(length-2) length-1 //approximate positions of each item
String[] split = new String[3];
if(tree.length() <= 2)//tree not long enough to process
return split;
split[0] = ""+tree.charAt(1);//put node in position zero
tree = tree.substring(2, tree.length()-1);//remove outer parens and node
int parenCount = 0;//count of open paren
int endLeftTree = 0;//end of left tree
for(int i = 0; i < tree.length(); i++)
{
if(tree.charAt(i) == '(')
parenCount++;
if(tree.charAt(i) == ')')
parenCount--;
if(parenCount == 0)
{
endLeftTree = i;
break;//ends loop once finding end of left tree
}
}
split[1] = tree.substring(0, endLeftTree+1);//left tree already removed the outer parens and node
split[2] = tree.substring(endLeftTree+1);//right tree
return split;
newTree = tree.substring(0, endLeftTree+1);
}
}
input (a(b()())(c(d())()))
output is
a,(b()()),(c(d)())
I need to further break to be able to print each split as a path, but with parenthesis removed.
Explanation / Answer
1.let us taqke a example:`
1
/
2 3
/
4 5
Step 1 Creates an empty stack: S = NULL
Step 2 sets current as address of root: current -> 1
Step 3 Pushes the current node and set current = current->left until current is NULL
current -> 1
push 1: Stack S -> 1
current -> 2
push 2: Stack S -> 2, 1
current -> 4
push 4: Stack S -> 4, 2, 1
current = NULL
Step 4 pops from S
a) Pop 4: Stack S -> 2, 1
b) print "4"
c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.
Step 4 pops again.
a) Pop 2: Stack S -> 1
b) print "2"
c) current -> 5/*right of 2 */ and go to step 3
Step 3 pushes 5 to stack and makes current NULL
Stack S -> 5, 1
current = NULL
Step 4 pops from S
a) Pop 5: Stack S -> 1
b) print "5"
c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything
Step 4 pops again.
a) Pop 1: Stack S -> NULL
b) print "1"
c) current -> 3 /*right of 5 */
Step 3 pushes 3 to stack and makes current NULL
Stack S -> 3
current = NULL
Step 4 pops from S
a) Pop 3: Stack S -> NULL
b) print "3"
c) current = NULL /*right of 3 */
Traversal is done now as stack S is empty and current is NULL.
program:
// non-recursive java program for inorder traversal
/* importing the necessary class */
import java.util.Stack;
/* Class containing left and right child of current
node and key value*/
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
/* Class to print the inorder traversal */
class BinaryTree {
Node root;
void inorder() {
if (root == null) {
return;
}
//keep the nodes in the path that are waiting to be visited
Stack<Node> stack = new Stack<Node>();
Node node = root;
//first node to be visited will be the left one
while (node != null) {
stack.push(node);
node = node.left;
}
// traverse the tree
while (stack.size() > 0) {
// visit the top node
node = stack.pop();
System.out.print(node.data + " ");
if (node.right != null) {
node = node.right;
// the next node to be visited is the leftmost
while (node != null) {
stack.push(node);
node = node.left;
}
}
}
}
public static void main(String args[]) {
/* creating a binary tree and entering
the nodes */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.inorder();
}
}