How should I practice Serialize and Deserialize a Binary Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Serialize and Deserialize a Binary Tree associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Serialize and Deserialize a Binary Tree

Google● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Source note: The interviewer asked: "Design an algorithm that serializes a binary tree into a string and can deserialize that string to fully restore the original tree structure." The candidate used preorder with # for empty nodes and commas between tokens. For the tree with root 3, left child 9, right child 100, and 48 as the left child of 100, they got 3,9,#,#,100,48,#,#,#. They brought up these edge cases themselves: an empty tree, one node, left-only or right-only subtrees, repeated values and negative values.

The report does not say the interviewer required this format, and it gives no limits. Here, the candidate's format is required so that answers can be checked. You do both directions in one call, on two separate inputs, and the rebuilt tree comes back in level order with trailing null values removed. The limits are practice choices.

The judged task matches the report at about 85%.

Design a way to turn a binary tree into a string and to rebuild the same tree from that string. Use this format:

Visit the tree in preorder: the node, then its left subtree, then its right subtree.
Write a node as its value, and write an empty child as #.
Join all the tokens with one comma, with no spaces.

So the empty tree is #, and one node with value 7 is 7,#,#.

You get two separate inputs, and they may describe different trees. Return an array of two strings:

The problem statement continues

Pro

Examples

Example 1

root = [3,9,100,null,null,48]data = "3,9,#,#,100,48,#,#,#"return = ["3,9,#,#,100,48,#,#,#","[3,9,100,null,null,48]"]

Write 3, then the left subtree: 9,#,#. Then the right subtree: 100, its left child 48,#,#, and its empty right child #. The string data describes the same tree, and in level order it is [3,9,100,null,null,48]. The two null values are the empty children of 9.

FastPrep Pro

Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

Full problem statement and constraints
2 more worked examples, explained
Guided hints and editorial
Run your code on real test cases

$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week

See Google hiring insights