FastPrepRecover a Tree From Preorder Traversal
Problems/Recover a Tree From Preorder Traversal

Recover a Tree From Preorder Traversal

Grammarly logoGrammarly● HardFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Grammarly technical phone screen, where the coding question was named only by its public number: rebuilding a binary tree from a preorder string in which dashes mark each node's depth.

The report gives no wording, examples or limits, so this page states that public problem in our own words with its usual rules and limits, including that an only child is a left child.

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

A binary tree was written out as one string by a preorder walk: the walk visits a node, then the node's left subtree, then its right subtree. For each node it visits, it writes D dashes followed by the node's value, where D is the depth of the node. The root has depth 0, and a child is one level deeper than its parent.

If a node has only one child, that child is its left child.

Given the string traversal, rebuild the tree and return its root.

Function

recoverFromPreorder(traversal: String) → TreeNode

Examples

Example 1

traversal = "5-3--1--4-8--9"return = [5,3,8,1,4,9]
return
531489
  • Read left to right: 5 has no dashes, so it is the root. 3 has one dash, so it is a child of 5, and it is the left one because it comes first.
  • 1 and 4 have two dashes, so they are the left and right children of 3, the node one level up that was read last.
  • 8 has one dash again: its parent is 5, whose left child is taken, so 8 is the right child. 9 is the only child of 8, so it is a left child.

Example 2

traversal = "7-12--15---3-9"return = [7,12,9,15,null,null,null,3]
return
7121539
  • Each of 12, 15 and 3 has one more dash than the node before it, so they form a chain of left children under 7.
  • 9 has one dash. The deepest node read so far that is one level up is the root 7, so 9 becomes its right child, jumping back up three levels.
  • Values can have more than one digit: 12 and 15 are single nodes, not 1 and 2.

Example 3

traversal = "1000000000"return = [1000000000]

There are no dashes, so the tree is a single node with value 1000000000.

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • 1 <= Node.val <= 10^9
  • traversal holds only digits and '-', and it is the string written for some binary tree by the rules above.

More Grammarly interview questions

  • Interval List IntersectionsPHONE SCREEN · Seen Nov 2026
  • First Target IndexPHONE SCREEN · Seen Jul 2026
  • Transactional Key-Value StoreONSITE INTERVIEW · Seen Aug 2026

Similar questions at other companies

  • Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
  • Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
  • Inorder Tree String EquivalenceGoogle · ONSITE INTERVIEWGoogle interview questions
  • Count Distinct Rooted-Tree GraftsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
  • Recover a Tree from Preorder Depth EncodingSuperhuman · PHONE SCREENSuperhuman interview questions
  • Account Roles With Parent-User InheritanceStripe · PHONE SCREENStripe interview questions
  • Find All Paths for a Name in a File SystemThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
  • Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
  • Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
  • Delete a Filesystem TreeDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions

Interview reports that mention this question

  • Grammarly SWE Phone Screen Questions: 1 Experience
See Grammarly hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        // Write your code here.
    }
}
Checking account…