Convert Ternary Expression to a Binary Tree

Question

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; public void addNode(Character data) { root = addNode(root, data); } private Node addNode(Node node, Character data) { if (node == null) { return new Node(data); } if (data < node.data) { node.left = addNode(node.left, data); } else { node.right = addNode(node.right, data); } 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); } } 

Answer 1

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).