Serialize and Deserialize Binary Tree
The problem
Create a representation of a binary tree that can reconstruct both its values and exact shape. Support empty trees and negative values.
Example
Root 5 with only right child 8 can serialize as "5,#,8,#,#".
Need a hint?
Values alone cannot distinguish different shapes.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Serialize in preorder, writing an explicit null marker for every absent child. Deserialize by consuming tokens once: a null marker returns null; a value creates a node whose left and right subtrees are recursively read next. Delimit values unambiguously and use a token list to avoid repeated string concatenation.
Complexity
O(n) tokens and O(n) space; character cost also includes the length of encoded values.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.