Question

You will be given several strings full of different keyboard characters, some of which are letters of the alphabet. Write a java program that creates a binary tree that uses only the alphabetical characters (a-z, A-Z) as the value within the leaf nodes using recursion and preorder traversal. All other values within the tree (either the root node or internal nodes) will be null. You may create any methods you see fit, so long as the final binary tree is correctly outputted to the console after completion using the preorder traversal method. Note that the alphabet characters do NOT have to be in any order (ASCII code, alphabetical, ect); the binary tree must be made in the order which they appear in the string.

An example of the string you may be supplied with is given below for testing purposes, as well as a graphical example to help visualize the tree:
*@m&a?pw

k k т. w

This means that, in order, the characters in the leaves of your binary tree should be: m, a, x, p, w, k

As a hint, use each character that is NOT an alphabet character as an indicator of an internal node. Note, however, that you will not have them in your console print-out at the end as they are only to be used to find where the leaf nodes of the binary tree are supposed to be created. All internal nodes may be considered null elsewise. The printout, as stated above, should be done using preorder traversal. Extra credit may be given to those who can also print inorder and postorder traversals, though these are not required.

Answer 1

The following code is a Java program that implements InOrder traversal of a Binary tree in which the alphabetical nodes in the given tree have been named as is and the unnamed nodes have been assigned numbers. If you require an output with just the alphabets, you can substitute the numbers in the code with a blank space. For our understanding of InOrder traversal, I have left them as numbers.

Code:

import java.util.Stack;

// BT = Binary Tree, T = tree, TN = TreeNode

public class Main {
public static void main(String[] args) throws Exception {
BT bt = BT.create();
bt.inOrder();
}
}

class BT {
static class TN {
String data;
TN left, right;
  
TN(String value) {
this.data = value;
left = right = null;
}
}

TN root;

public void inOrder() {
inOrder(root);
}

private void inOrder(TN node) {
if (node == null) {
return;
}

inOrder(node.left);
System.out.printf("%s ", node.data);
inOrder(node.right);
}

public static BT create() {
BT T = new BT();
TN root = new TN("1");
T.root = root;

T.root.left = new TN("2");
T.root.right = new TN("k");

T.root.left.left = new TN("m");
T.root.left.right = new TN("3");

T.root.left.right.left = new TN("a");
T.root.left.right.right = new TN("4");

T.root.left.right.right.left = new TN("p");
T.root.left.right.right.right = new TN("w");
  
return T;
}
}

Output:

m 2 a 3 p 4 w l k