Decode a Tree From Text
MediumTrees
Problem
The receiving end gets a string produced by this encoding: the nodes of a binary tree in pre-order (node, left subtree, right subtree), each value as a decimal integer, each missing child as #, separated by commas.
For example "1,2,#,#,3,4,#,#,5,#,#" is the tree [1, 2, 3, null, null, 4, 5] and "#" is the empty tree. Rebuild the tree from data and return its root.
Example 1
- Input:
- data = "1,2,#,#,3,4,#,#,5,#,#"
- Output:
- [1, 2, 3, null, null, 4, 5]
1 is the root; '2,#,#' is its whole left subtree; '3,4,#,#,5,#,#' its right subtree.
Example 2
- Input:
- data = "#"
- Output:
- []
Constraints
- data is a valid encoding of a tree with 0 ≤ n ≤ 10^4 nodes
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
After reading a node's value, what do the next tokens describe?
Walkthrough
How to approach it
01Clarify before coding
- Is the input always valid? Yes, so no error handling for malformed strings is needed.
- Can values be negative or zero? Yes; parse with int, and do not treat '0' as a marker.
- How deep can the tree be? Up to 10^4, so prefer an explicit stack over recursion in Python.
02Brute force
Recursively: read a token; if '#', return empty; else create the node and recursively read its left and then its right subtree.
Cost: O(n) time, which is optimal, but O(h) recursion that can reach 10^4 frames on a chain and overflow Python's default limit.
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.