Skip to main content
All Questions

Serialize and deserialize binary tree

Hard
Unlock detailed company stats for this questionUpgrade

Serialization turns a data structure into a string so it can be stored or sent somewhere, and deserialization rebuilds the structure from that string.

Design a Codec class with two methods: serialize(root), which turns a binary tree into a string, and deserialize(data), which turns that string back into an identical tree. You choose the string format. The tests check that deserializing the serialized string rebuilds the original tree, using a separate Codec object for each call.

Trees in the examples and tests are written in level order, with null for a missing child.

Example 1

Input: root = [1, 2, 3, null, null, 4, 5] Output: [1, 2, 3, null, null, 4, 5] 1 / \ 2 3 / \ 4 5

One possible serialization is "1,2,#,#,3,4,#,#,5,#,#", where # marks a missing child.

Example 2

Input: root = [] Output: []

An empty tree has to survive the round trip too.

Constraints

  • The tree has between 0 and 10^4 nodes.
  • -1000 <= Node.val <= 1000

Related courses

Course

Data Engineering Interview Prep

Land your dream data engineering role at Meta, Google, Amazon, Microsoft, Walmart, DoorDash, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Practice data modeling, pipeline design, SQL, coding, behavioral interviews, and more.

Course

Software Engineering Interview Prep

Land your dream software engineering role at Google, Amazon, Microsoft, Meta, Apple, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates—practice data structures, algorithms, system design, people management, behavioral interviews, and more.