Convert a ternary expression to a tree


  • 0
    N

    Convert a ternary expression to a tree.

    For example:

    a?b:c
    
    
      a
     / \
    b   c
    
    a?b?c:d:e
    
        a 
       / \ 
      b   e
     / \
    c   d
    
    a?b:c?d:e
    
       a
      / \
     b   c
        / \
       d   e
    

  • 0
    F

    SPOILER ALERT!

    A possible algorithm would be to perform a DFS. It requires a stack and one iteration of the ternary expression string. The loop over the string would do the following:

    - add the current element to the tree
    ! - if next char is '?': push a pointer to the right child of the current tree node to the stack
    ! - else: pop an element from the stack

    Time: O(n)
    ! Space: 0(n)


  • 0

    @fjabalera Welcome to the new Discuss!

    You can use the spoiler notation like this:

    >! Spoiler
    

  • 0
    F

    @1337c0d3r edited, thanks!


  • 0

    Here is a recursion solution . I hope someone to publish better one implemented with stack.Each time I find ''?" I create new left child of currect root, when I find ":" I move the pointer to then next character.

    private int pos = 1;
    void createTree(String expr, TreeNode root) {
    	if  (pos  ==  expr.length())
    	 	return;
    	if (expr.charAt(pos) == ':') 
    		pos++;
    	else {
    	    if (expr.charAt(pos) == '?') {
    		    root.left = new TreeNode(expr.charAt(pos +1));
    		    pos += 2;
    		    createTree(expr, root.left);
    	    }		
                if((expr.charAt(pos) != ':') && (expr.charAt(pos) != '?')) 
    	   {
    	           root.right = new TreeNode(expr.charAt(pos));
    	           pos += 1;
    	           createTree(expr,root.right);
    	    }	
       }
    }
    
     TreeNode root = new TreeNode('a');
     createTree("a?b?c?d:k:l?m:h?a:s:i",root);

  • 0
    I

    My C++ solution

    void AddTotree(string str, Tree *node, int i){
    	
    	Tree * next;
    	if(i + 2 <str.length() ){
    		next = new Tree(str[i+2]);
    	}
    	else{
    		return;
    	}
    
    	if(str[i +1] == '?'){
    		node->left = next;
    		next->parent = node;
    	}
    
    	if(str[i+1] == ':'){
    
    		Tree* n = node->parent;
    		if(n == NULL) return;		//Expression is wrong
    		while(n->right != NULL){
    			n = n->parent;
    		}
    		n->right = next;
    		next->parent = n;
    	}
    
    	
    	AddTotree(str, next, i+2);
    
    }
    

  • 0
    R

    My solution.

    English description:

    I start with a stack data structure with an empty node in it and iterated through the expression once. For every character, I follow this rule.
    1. if '?', peek at the top of stack and initialize left node. Push left node to stack
    2. if ':', pop the top node in the stack, then peek at the top. Initialize right node and push right node to stack
    3. if character, peek at top node and set value to that node

    Node ternaryToTree(String exp) {
            Stack stack = new Stack();
            Node node = new Node();
            stack.push(node);
            for(int i = 0; i < exp.length(); i++) {
                    char c = exp.charAt(i);
                    if(c == '?') {
                            stack.peek().left = new Node();
                            stack.push(stack.peek().left);
                    } else if(c == ':') {
                            stack.pop();
                            stack.peek().right = new Node();
                            stack.push(stack.peek().right);
                    } else {
                            stack.peek().val = c;
                    }
            }
            return node;
    }
    

Log in to reply
 

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