Ternary Expression to Binary Tree


  • 2
    L

    Convert a ternary expression to a binary tree.

    Say:

    a?b:c to

      a
     /  \
    b   c
    

    a?b?c:d:e to

         a
        / \
       b   e
      / \
     c   d
    

    Also, think about "a?b:c?d:e"


  • 19

    Let's assume the input ternary expression is valid, we can build the tree in preorder manner.

    Each time we scan two characters, the first character is either ? or :, the second character holds the value of the tree node. When we see ?, we add the new node to left. When we see :, we need to find out the ancestor node that doesn't have a right node, and make the new node as its right child.

    Time complexity is O(n).

    public TreeNode convert(char[] expr) {
      if (expr.length == 0) {
        return null;
      }
      
      TreeNode root = new TreeNode(expr[0]);
      
      Stack<TreeNode> stack = new Stack<>();
      
      for (int i = 1; i < expr.length; i += 2) {
        TreeNode node = new TreeNode(expr[i + 1]);
        
        if (expr[i] == '?') {
          stack.peek().left = node;
        }
        
        if (expr[i] == ':') {
          stack.pop();
          while (stack.peek().right != null) {
            stack.pop();
          }
          stack.peek().right = node;
        }
        
        stack.push(node);
      }
      
      return root;
    }

  • 6
    E

    I think you need to push the root into the stack first before starts the loop.


  • 0
    C

    Good solution! thank you


  • 1
    J

    I'm wondering if you should put the root node to the stack at first


  • 1

    I agree with that you should push root into the stack first.


  • 2
    S

    @jeantimex : Thanks. This solutions works considering we add root node on stack as others have suggested.

    So, based on your algorithm, i have added a Python solution and a test case.

    from commons.stack import Stack      # import custom Stack class 
    
    class Node(object):
        """  Tree Node """
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right
    
    
    def inorder_tree(node, result):
       """ Access Tree in-order """
        if node is not None:
            inorder_tree(node.left, result)
            result.append(node.data)
            inorder_tree(node.right, result)
    
    
    def ternary_to_binary_tree(expression):
        """ Convert ternary expression to Binary Tree """
        if not expression:
            return None
    
        # Assuming the expression is of correct form
        stack = Stack()
        root = Node(expression[0])
        stack.push(root)
    
        for index in range(1, len(expression), 2):
            operator = expression[index]
            next_char = expression[index + 1]
            node = Node(next_char)
            if operator == "?":
                stack.peek().left = node
    
            if operator == ':':
                stack.pop()
                while(stack.peek().right != None):
                    stack.pop()
                stack.peek().right = node
    
    
            stack.push(node)
    
        return root
    
    if __name__ == '__main__':
        test = "a?b?c:d:e"
        root_node = ternary_to_binary_tree(test)
        expected_result = ['c', 'b', 'd', 'a', 'e']
        actual_result = []
        # In-order traversal done to test the output
        inorder_tree(node=root_node, result=actual_result)
        assert expected_result == actual_result
    
    

  • 0

    @jeantimex What if the a is "xxx> 3" ? i+= 2 is not a good move.


  • 0
    P

    @jeantimex
    I'd like to ask why do we need the while loop here:

    while (stack.peek().right != null) {
    stack.pop();
    }


  • 1
    P

    If the input is valid, I think using two pop() instead of using the while loop would work. Is that right?

    public TreeNode convert(char[] expr) {
            if (expr.length == 0) {
                return null;
            }
            TreeNode root=new TreeNode(expr[0]);
            Stack<TreeNode> stack=new Stack<>();
            queue.add(root);
            for(int i=1;i<expr.length;i+=2){
                if(expr[i]=='?'){
                    TreeNode node=new TreeNode(expr[i+1]);
                    stack.peek().left=node;
                    stack.push(node);
                }else if(expr[i]==':'){
                    stack.pop();
                    TreeNode cur=stack.pop();
                    TreeNode node=new TreeNode(expr[i+1]);
                    cur.right=node;
                    stack.push(node);
                }
            }
            return root;
        } 
    

  • 0
    C

    @perfecttt I agree with you. I think your code is more intuitive. But I am not sure in the interview is there any test case that cannot pass through your code.


  • 0
    L
    This post is deleted!

  • 0
    A

    @perfecttt so the reason why we need that while loop is that imagine we have just filled up the rightmost child of a left subtree (in the examplee)
    ie:
    String input = "a?b?c?d:e:f?g:h:i?j:k"
    0_1508773388293_f69fcb01-2f6b-4bfc-ada2-e5c456b2491c-image.png

    imagine you just placed h into your tree, your current index is pointing to ":i" and thus are now trying to insert i- at that point your stack (from top to bottom) looks like h,f,b,a
    we need to pop one node to remove a sibling node, and then keep popping nodes off till we reach a, which at this time has no right child (hence the whole while loop you are asking about)

    hopefully that clears it up, but if not go ahead and trace through "a?b?c?d:e:f?g:h:i?j:k" for yourself:)

    cheers!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.