FastPrep
Problem · Tree

Recover a Tree from Preorder Depth Encoding

Learn this problem
● HardSuperhuman logoSuperhumanFULLTIMEPHONE SCREEN

Problem statement

A binary tree is serialized by a preorder traversal. Each node is written as its positive integer value, preceded by a number of hyphens equal to its depth. The root has depth 0.

For this exercise, assume every node has at most two children. When a node has exactly one child, that child is its left child. The input is a valid encoding of exactly one tree.

Given the serialized string traversal, reconstruct the tree and return its root.

Function

recoverFromPreorder(traversal: String) → TreeNode

Examples

Example 1

traversal = "1-2--3--4-5--6--7"return = [1,2,5,3,4,6,7]

Depth 0 gives root 1. The depth-1 nodes are 2 and 5; each receives its following depth-2 nodes as children.

Example 2

traversal = "1-2--3---4-5--6---7"return = [1,2,5,3,null,6,null,4,null,7]

The depth increases from 2 to 3 before values 4 and 7, so they become the left children of 3 and 6.

Example 3

traversal = "1-401--349---90--88"return = [1,401,null,349,88,90]

After the depth-3 node 90, the encoding returns to depth 2, so 88 becomes the right child of 401.

Constraints

  • 1 <= number of nodes <= 1000.
  • 1 <= node.val <= 10^9.
  • traversal contains only decimal digits and hyphens.
  • traversal is a valid preorder depth encoding under the stated one-child rule.

More Superhuman problems

drafts saved locally
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 * }
 */
public TreeNode recoverFromPreorder(String traversal) {
  // write your code here
}
traversal"1-2--3--4-5--6--7"
expected[1,2,5,3,4,6,7]
checking account