How to convert a Ternary expression to a Binary tree structure?

Question

I came across this problem that has Ternary expression (a?b:c) and needs the ternary expression to be converted into a Binary tree structure.

     a?b:c 

       a
      / \
     b   c

  a?b?c:d:e

     a
    / \
   b   e
  / \
 c   d

My approach using a Binary tree implemented using a array :-

Parent resides at - i Left child - 2i Right child - 2i+1

Start parsing the ternary expression the first character will form the root node so it will be at position 1 in the array. If the next character is a '?' then the characters that follow will be its children so left child (b in this case will be at position 2). If the next character is a ":" then we have found the right child (c in the first case) so we add that to position 3.

In the second case we face a "?" after b so whatever follows will be its children and will be added to 2j and 2j+1 respectively where j is the position of b in the array.Now we face a ":" we check the parent of the current child if it has two children then we backtrack and check the previous node until we find a node that is missing a right child.

Is there any other way to do this? Hope I have been articulate enough.

Answer 1

Below is my solution which has been tested thoroughly.

class TreeNode {
    char c;
    TreeNode left;
    TreeNode right;

    TreeNode(char c) {
        this.c = c;
        left = null;
        right = null;
    }
}

public TreeNode tenaryToTree(String s) {
    if (s.length() == 0) {
        return null;
    }

    TreeNode root = new TreeNode(s.charAt(0));
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == '?') {
            TreeNode node = stack.peek();
            node.left = new TreeNode(s.charAt(i + 1));
            stack.push(node.left);
        } else if (s.charAt(i) == ':') {
            stack.pop();
            TreeNode node = stack.pop();
            node.right = new TreeNode(s.charAt(i + 1));
            stack.push(node.right);
        }
    }

    return root;
}

Answer 2

This one would be without using parent node. But using stack.

    public NodeC convertTtoBT (char[] values) {
    char xx = values[0];
    NodeC n = new NodeC(xx);
    Stack<NodeC> a =  new Stack<NodeC>();
    for (int i = 1; i < values.length; i += 2) {
        if (values[i] == '?') {
            n.left = new NodeC (values[i + 1]);
            a.add(n);
            n = n.left;

        }
        else if (values[i] == ':') {
            n = a.pop();
            while (n.right != null) {
                n = a.pop();
            }             
            n.right = new NodeC (values[i + 1]);
            a.add(n);
            n = n.right;
        }
    }
    return n;
}

Answer 3

Walk through the expression from right to left, pushing any letters as nodes to the stack. If you see '?', then instead of pushing the next letter, take it as the root, pop two last nodes from the stack as left and right root's children, and push the root back into the stack.

public TreeNode ternaryToTree(char[] exp) {
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

    for (int i = exp.length-1; i >= 0; i--) {
        if (exp[i] == ':') continue;
        if (exp[i] == '?') {
            TreeNode node = new TreeNode(exp[--i]);
            node.left = stack.pop();
            node.right = stack.pop();
            stack.push(node);
        } else {
            stack.push(new TreeNode(exp[i]));
        }
    }

    return stack.isEmpty() ? null : stack.pop();
}

Answer 4

if this a?b:c?d?e:f:g?h:i?j:k is the ternary expression then tree would be like this

          a
         / \
        b   c
           /  \
          d    g
         / \  / \
        e   f h  i
                / \
               j   k

Below is the Java solution...

private static TreeNode convertTernaryExpression(String s) 
{

    Stack<TreeNode> stack = new Stack<>();

    int length = s.length();
    int index = 0;
    TreeNode rootNode = null;
    while(index < length)
    {
        while(s.charAt(index) != ':')
        {
            if(s.charAt(index) == '?' && stack.peek().right != null)
            {
                TreeNode temp = stack.pop();
                if(rootNode == null)
                {
                    rootNode = temp;
                }
                stack.push(temp.right);
            }
            stack.push(new TreeNode(s.charAt(index++)));
        }

        TreeNode left = stack.pop();
        TreeNode questionMark = stack.pop();
        TreeNode root = stack.pop();
        index++;
        TreeNode right = new TreeNode(s.charAt(index++));

        root.left = left;
        root.right = right;

        stack.push(root);
    }

    if(rootNode == null)
    {
        return stack.pop();
    }
    else
    {
        return rootNode;
    }
}

class TreeNode
{
    TreeNode left;
    TreeNode right;
    char val;
    public TreeNode(char val) 
    {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

Answer 5

I came up with something like this using trees. Not tested thoroughly:

When I see a '?', it's my left child, so add to my left and go left.

If I see ':', then:

1. Go to my parent
2. If right is not null and parent is not not null, keep going to my parent
3. My right child is empty. Add right. Go to right.

Note: You will never go back to the root if it has a right child.

    public NodeC convertTtoBT (char[] values) {
    NodeC n = new NodeC (values[0]);

    for (int i = 1; i < values.length; i += 2) {
        if (values[i] == '?') {
            n.left = new NodeC (values[i + 1]);
            n = n.left;
        }
        else if (values[i] == ':') {
            n = n.parent;
            while (n.right != null && n.parent != null ) {
                n = n.parent;
            }                    
            n.right = new NodeC (values[i + 1]);
            n = n.right;
        }
    }
    return n;

Answer 6

Idea is to start parsing the string from left to right and when you come across a '?' you go deeper in the tree else just return the new node created.

Here is my recursive solution :

  struct node{
    char val;
    node *left;
    node *right;
    node(char v):val(v),left(NULL),right(NULL){
    }
};

    node* create_tree(string input, int &current){
    if(current>=(int)input.size()){
        return NULL;
    }
    node *temp = new node(input[current]);
    current+=2;
    if(current<(int)input.size()){
        if(input[current-1]=='?'){
            temp->left=create_ternary_tree(input,current);
            temp->right=create_ternary_tree(input,current);
        }
    }
    return temp;
}