Recover a Tree From Preorder Traversal
Updated
Problem statement
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) → TreeNodeExamples
Example 1
traversal = "5-3--1--4-8--9"return = [5,3,8,1,4,9]- Read left to right:
5has no dashes, so it is the root.3has one dash, so it is a child of5, and it is the left one because it comes first. 1and4have two dashes, so they are the left and right children of3, the node one level up that was read last.8has one dash again: its parent is5, whose left child is taken, so8is the right child.9is the only child of8, so it is a left child.
Example 2
traversal = "7-12--15---3-9"return = [7,12,9,15,null,null,null,3]- Each of
12,15and3has one more dash than the node before it, so they form a chain of left children under7. 9has one dash. The deepest node read so far that is one level up is the root7, so9becomes its right child, jumping back up three levels.- Values can have more than one digit:
12and15are single nodes, not1and2.
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^9traversalholds only digits and'-', and it is the string written for some binary tree by the rules above.
More Grammarly interview questions
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