## Sunday, November 29, 2015

### Pocket Gems - Ternary Expression to Binary Tree

Pocket Gems - Ternary Expression to Binary Tree - - 博客频道 - CSDN.NET
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``````
http://stackoverflow.com/questions/28487831/how-to-convert-a-ternary-expression-to-a-binary-tree-structure
http://yuanhsh.iteye.com/blog/2206191
1. public TreeNode convertToBT (char[] values) {
2.     TreeNode root = new TreeNode(values[0]);
3.     TreeNode n = root;
4.     Stack<TreeNode> a =  new Stack<TreeNode>();
5.     for (int i = 1; i < values.length; i += 2) {
6.         if (values[i] == '?') {
7.             n.left = new TreeNode (values[i + 1]);
9.             n = n.left;
10.
11.         }
12.         else if (values[i] == ':') {
13.             n = a.pop();
14.             while (n.right != null) {
15.                 n = a.pop();
16.             }
17.             n.right = new TreeNode (values[i + 1]);
19.             n = n.right;
20.         }
21.     }
22.     return root;
23. }
https://leetcode.com/discuss/66620/ternary-expression-to-binary-tree
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;
}``````
https://discuss.leetcode.com/topic/108/convert-a-ternary-expression-to-a-tree/2
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);``````
https://github.com/interviewcoder/leetcode/blob/master/src/s09_ConvertTernaryExpressionToBinaryTree/Solution.java
* 1. Does node have parent pointer?
* 2. Expression's format, leading, trailing spaces, spaces between characters?
* 3. May expression be illegal?
* 4. Token's length is always 1?
Read full article from Pocket Gems - Ternary Expression to Binary Tree - - 博客频道 - CSDN.NET