# Sharing two C++ solutions: one pass 12ms solution and DFS 6ms solution

• 1. One pass solution:
Time complexity: O(n)
The ternary expression is essentially a pre-order DFS of a corresponding binary tree, so the one pass solution is trying to rebuild the tree with the help of a stack.

Two possible cases:

Whenever we meet a ?, this means the previous node is a non-leaf node, and we need to update its type.
Whenever we meet a :, this means the previous node is either a leaf node, and we need to update the leaf value and do a bottom up traversal to connect the children with their parents, and we can update the expression decision on-the-fly.

``````    struct Node {
bool hasLeft;
bool hasRight;
char type;
char value;
Node() : type(-1), value(-1), hasLeft(false), hasRight(false) {};
};
string parseTernary(string expression) {
vector<Node> roots;
roots.push_back(Node());

for (int i=0; i<=expression.size(); i++) {
char c = i == expression.size() ? ':' : expression[i];
if (c == '?') {
roots.back().type = expression[i-1];
roots.push_back(Node());
} else if (c == ':') {
roots.back().hasLeft = true;
roots.back().hasRight = true;
roots.back().value = expression[i-1];
while (roots.size() > 1 && roots.back().hasLeft && roots.back().hasRight) {
Node node = roots.back();
roots.pop_back();
if (!roots.back().hasLeft) {
if (roots.back().type == 'T') roots.back().value = node.value;
roots.back().hasLeft = true;
} else {
if (roots.back().type == 'F') roots.back().value = node.value;
roots.back().hasRight = true;
}
}
if (i < expression.size()) roots.push_back(Node());
}
}

string result;
result += roots.back().value;
return result;
}
``````

2. DFS solution:
Time Complexity: O(nk) where k is the recursion depth, which can be as bad as k.
Another way to look at it is that, still a binary tree, but we can at each level decide to go left or right based on the current 'T' or 'F' on the parent node. This is essentially a pre-order traversal again.

The pre-order traversal works as the following:

At each level, we need to dive the expression into left child and right child by going over the expression and find out the outermost matching pair of '?' and ':', we can maintain a counter for '?' and increment that when we hit a '?' and decrement when we hit ':' until the counter reaches zero.

The base case for this DFS is that if there's no subexpression, we can quickly branch out as a leaf (since leaf only contains one char)

Then call recursion on left child or right child based on the parent value.

``````    string parseTernary(string expression) {
if (expression.empty()) return expression;
char val = evaluateSubExpression(expression, 0, expression.size()-1);
string result;
result += val;
return result;
}

char evaluateSubExpression(const string& expr, int start, int end) {
if (start == end) return expr[start];
int op1 = -1;
int op2 = -1;
int depth = 0;

for (int i=start; i <= end; i++) {
if (expr[i] == ' ') continue;
if (expr[i] == '?') {
depth++;
if (op1 == -1) op1 = i;
} else if (expr[i] == ':') {
if ((--depth) == 0) {
op2 = i;
break;
}
}
}

if (expr[start] == 'T') {
return evaluateSubExpression(expr, op1+1, op2-1);
} else {
return evaluateSubExpression(expr, op2+1, end);
}
}
``````

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