binary-treeternary-operatordata-conversion

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


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.


Solution

  • 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;
    }