FastPrepTernary Expression to Binary Tree
Problems/Ternary Expression to Binary Tree

Ternary Expression to Binary Tree

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Nutanix campus hiring process for interns, in August 2018. The first question in the interview, after a written debugging round, was to turn a ternary string into a tree. Example 1 uses the report's sample string.

The report does not say which part goes to which child, how to return the tree, or any sizes. Here the part after '?' becomes the left child, and the part after ':' becomes the right child. You return the tree in level order, with "#" for a missing child and the "#" entries at the end removed. Every condition and value is one lowercase letter. Letters can repeat. The expression is always valid, and it has at most 1001 characters.

Our version is about 85% the same as the reported question.

A ternary expression is built from lowercase letters and the symbols ? and : by these rules:

  • A single letter is an expression.
  • If c is a letter and X and Y are expressions, then c?X:Y is an expression. It reads as: if c, then X, otherwise Y.

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:

  1. Write the root's letter first.
  2. 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.
  3. 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 <= 1001
  • expression is a valid ternary expression built by the rules above, and every letter in it is a lowercase English letter.
See Nutanix hiring insights
Saved
class Solution {
    public String[] ternaryToTree(String expression) {
        // Write your code here.
    }
}
Checking account…