# Convert Ternary Expression to a Binary Tree

This is programming question I came across (geeksforgeeks) : Given a string that contains ternary expressions. The expressions may be nested, task is convert the given ternary expression to a binary Tree.Any feedback appreciated.

All the required classes are added as members. I am using a simple recursive approach to build the tree. Each time a '?' expression is encountered then the next element is added as the left node.Similarly, each time a ':' expression is encountered then the next element is added as the right node.

 Input :  string expression =   a?b:c
Output :        a
/  \
b    c

Input : expression =  a?b?c:d:e
Output :     a
/  \
b    e
/  \
c    d


The Code:

public class TernaryExpressionToBinaryTree {

public class Node {
private Character data;
private Node left;
private Node right;

public Node(Character data) {
this.data = data;
}
}

public class BST {
public Node getRoot() {
return root;
}

public void setRoot(Node root) {
this.root = root;
}

public Node root;

}

private Node addNode(Node node, Character data) {
if (node == null) {
return new Node(data);
}
if (data < node.data) {
} else {
}
return node;
}
}

/*
Preorder traversal
*/
public void displayTree(Node node) {
if (node != null) {
System.out.print(node.data + " | ");
displayTree(node.left);
displayTree(node.right);
}
}
public Node buildTreeFromTernaryExpression(Node node, String expression, int index) {

// check corner cases
if (expression == null || expression.trim().isEmpty() || index < 0 || index > expression.length()) {
return null;
}
// if its is a valid character
if (node == null || index == 0 || expression.charAt(index) != '?' || expression.charAt(index) != ':') {
node = new Node(expression.charAt(index));
}
//if it is a valid expression ? or :
if ((index + 1) < expression.length()-1 && expression.charAt(index + 1) == '?') {
node.left = buildTreeFromTernaryExpression(node.left, expression, index + 2);
}

if ((index + 1) < expression.length()-1 && expression.charAt(index + 1) == ':') {
node.right = buildTreeFromTernaryExpression(node.right, expression, index + 2);
}
return node;
}

public static void main(String args[]) {
TernaryExpressionToBinaryTree ternaryExpressionToBinaryTree = new TernaryExpressionToBinaryTree();
Node root = ternaryExpressionToBinaryTree.buildTreeFromTernaryExpression(null, "a?b?c:d:e", 0);
ternaryExpressionToBinaryTree.displayTree(root);
}
}


1. You can delete the BST class. You don't use it anywhere.
2. Error handling looks weird to me. I suggest throwing an exception if the input is invalid. You also don't check all possible cases. For instance, you code prints a tree ? | a | b | for the input ??a:b, which is clearly invalid. I'd recommend either adding proper error handling or just dropping it altogether (the problem statement says that the string is a ternary expression, anyway).
3. Comments should not repeat the code. If you have something like // if it is a valid character, it's a good indicator that the following check should be moved to a separate method with a proper name (something like private boolean isValidCharacter(Node node, String expression, int index).
• Are TernaryExpressionToBinaryTree, ternaryExpressionToBinaryTree, and buildTreeFromTernaryExpression acceptable as variable/class/method names? they seem to pollute the code and are quite long. – ljeabmreosn Jun 16 '17 at 22:48