Encode a Tree as Text
MediumTrees
Problem
To send a binary tree over a wire, it must be turned into a single string. Use this exact format: list the nodes in pre-order (node, left subtree, right subtree), writing each node's value as a decimal integer and each missing child as #, with tokens separated by commas and no spaces.
So a lone node 7 encodes as "7,#,#" and the empty tree as "#". Return the encoded string of root.
Example 1
- Input:
- root = [1, 2, 3, null, null, 4, 5]
- Output:
- "1,2,#,#,3,4,#,#,5,#,#"
1, then its left subtree (2 with two missing children), then its right subtree 3(4, 5).
Example 2
- Input:
- root = []
- Output:
- "#"
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
Why must missing children be written down at all?
Walkthrough
How to approach it
01Clarify before coding
- Is the format fixed? Yes, exactly as described, so the output is unique.
- Negative values? Yes, written with a leading minus.
- Trailing comma or spaces? Neither.
02Brute force
Write the tree as a full level-order array including every null position, then join it.
Cost: A deep, thin tree has exponentially many null positions at the bottom levels if every slot is listed: unbounded output.
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.