Rebuild a Tree From a Dashed Outline
HardTrees
Problem
An org chart was exported as a single line of text. It lists the nodes of a binary tree in pre-order; before each value come d dashes, where d is that node's depth (the root has depth 0, so no dashes). Values are non-negative integers that may have several digits.
Whenever a node has exactly one child, it is always the left child. Rebuild the tree from outline and return its root.
Example 1
- Input:
- outline = "1-2--3--4-5--6--7"
- Output:
- [1, 2, 5, 3, 4, 6, 7]
2 and 5 are at depth 1 (children of 1); 3, 4 under 2 and 6, 7 under 5 are at depth 2.
Example 2
- Input:
- outline = "1-2--3---4-5--6---7"
- Output:
- [1, 2, 5, 3, null, 6, null, 4, null, 7]
Example 3
- Input:
- outline = "1-401--349---90--88"
- Output:
- [1, 401, null, 349, 88, 90]
Constraints
- 1 ≤ number of nodes ≤ 1000
- 0 ≤ node.val ≤ 10^9
- The outline is valid.
Hint
Show the first hint
Reading left to right, when you meet a node at depth d, which earlier node must be its parent?
Walkthrough
How to approach it
01Clarify before coding
- Can values have several digits? Yes, so read digits until the next dash.
- Is a single child always on the left? Yes, which makes the tree unique.
- Is the input guaranteed valid? Yes.
02Brute force
Parse into (depth, value) pairs, then for each node scan backwards for the closest earlier node at depth - 1.
Cost: O(n²) time in the worst case because of the backward scans.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.