PPractick

The problem

A distributed cache must store binary trees as strings and later rebuild them exactly, including their shape. Preorder with an explicit marker for missing children does it compactly: write the node's value, then serialise its left subtree, then its right subtree, and write # for every null. Because every null is recorded, the string encodes the shape unambiguously, and deserialisation just reads the tokens back in the same preorder.

Example: [1, 2, 3, null, null, 4, 5] → "1,2,#,#,3,4,#,#,5,#,#" → the same tree.

Function signature

class Codec {
public:
    string serialize(TreeNode* root);
    TreeNode* deserialize(const string& data);
};

Test cases

Input (level order)	Serialized	Rebuilt (level order)
[1, 2, 3, null, null, 4, 5]	"1,2,#,#,3,4,#,#,5,#,#"	[1, 2, 3, null, null, 4, 5]
[]	"#"	[]
[1]	"1,#,#"	[1]
[-5, 10]	"-5,10,#,#,#"	[-5, 10]
[1, null, 2, null, 3]	"1,#,2,#,3,#,#"	[1, null, 2, null, 3]

(Confirm: values can be negative or repeated; the format is free as long as deserialize(serialize(t)) rebuilds t exactly.)

How interviewers phrase it

• "Design an algorithm to serialize a binary tree to a string and deserialize the string back to the original tree structure" (LeetCode 297).

Clarifying questions to ask

1. Any format constraints? (No: any self-consistent format.)
2. Can values be negative or repeated? (Yes, so separators are needed and values can't identify nodes.)
3. Is the size of the string important? (It's O(n) either way.)

Follow-ups to expect

1. "Why record nulls?"
2. "Why does deserialisation work with one pointer?"
3. "Level-order format instead?"
4. "What about BSTs?"
5. "Complexity?"

Related questions

• Letter Combinations of a Phone Number Hard
• Palindrome partitioning Hard
• Expression Add Operators Hard
• Implement Min Stack Hard
• LFU Cache Hard
• Longest Repeating Character Replacement Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in