Ternary Expression to Binary Tree
Updated
Problem statement
A ternary expression is built from lowercase letters and the symbols ? and : by these rules:
- A single letter is an expression.
- If
cis a letter andXandYare expressions, thenc?X:Yis an expression. It reads as: ifc, thenX, otherwiseY.
The same letter may appear more than once.
Turn expression into a binary tree. A single letter becomes a node with no children. For c?X:Y, the letter c becomes a node whose left child is the tree of X (the true part) and whose right child is the tree of Y (the false part).
Return the tree as a list in level order:
- Write the root's letter first.
- Then take the nodes in the order their letters were written. For each one, write its left child and then its right child: the child's letter, or
"#"if that child is missing. - When no nodes are left, remove every
"#"at the end of the list.
Function
ternaryToTree(expression: String) → String[]Examples
Example 1
expression = "a?b?c:d:e"return = ["a","b","e","c","d"]The root is a. Its true part is b?c:d and its false part is e, so b is the left child and e is the right child of a. Inside the true part, c and d become the left and right children of b.
Level order lists a, then b and e, then c and d. The children of e, c and d are all missing, so the list would end with six "#" entries, and they are removed.
Example 2
expression = "a?b:c?d:e"return = ["a","b","c","#","#","d","e"]Here the second ? is inside the false part: a has left child b and right child c, and c has children d and e.
In level order, a comes first, then b and c. Next come the two missing children of b as "#", then d and e. These two "#" entries stay because real nodes come after them.
Example 3
expression = "x"return = ["x"]A single letter is a tree with one node and no children.
Constraints
1 <= expression.length <= 1001expressionis a valid ternary expression built by the rules above, and every letter in it is a lowercase English letter.