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