4
\$\begingroup\$

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);
    }
}
\$\endgroup\$
4
\$\begingroup\$
  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).

\$\endgroup\$
  • \$\begingroup\$ Are TernaryExpressionToBinaryTree, ternaryExpressionToBinaryTree, and buildTreeFromTernaryExpression acceptable as variable/class/method names? they seem to pollute the code and are quite long. \$\endgroup\$ – ljeabmreosn Jun 16 '17 at 22:48
  • \$\begingroup\$ @ljeabmreosn The name should accurately reflect the purpose of a class/method. It's fine that it's long. \$\endgroup\$ – kraskevich Jun 17 '17 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.