Serialize and Deserialize a Binary Tree
Updated
Problem statement
Design a way to turn a binary tree into a string (serialize) and to rebuild the tree from that string (deserialize). Use this format:
- List the tree in preorder: the node, then its left subtree, then its right subtree.
- Write a node as its value and an empty child as
#. - Put one comma between tokens, with no spaces.
So the empty tree is #, and a single node with value 4 is 4,#,#.
You get two separate inputs, which may describe different trees. Return an array of two strings:
- the serialization of the tree
root, and - the tree rebuilt from the string
data, written in level order as[v1,v2,...]: list the nodes level by level from left to right, writenullfor an empty child of a node, and remove allnullvalues at the end. The empty tree is[].
Function
serializeAndDeserialize(root: TreeNode, data: String) → String[]Examples
Example 1
root = [1,2,3,null,null,4,5]data = "1,2,#,#,3,4,#,#,5,#,#"return = ["1,2,#,#,3,4,#,#,5,#,#","[1,2,3,null,null,4,5]"]Preorder visits 1, then its left subtree (2, whose two children are empty, written #,#), then its right subtree (3, then 4 with two empty children, then 5 with two empty children). That gives 1,2,#,#,3,4,#,#,5,#,#. Here data describes the same tree, so rebuilding it and writing it in level order gives [1,2,3,null,null,4,5].
Example 2
root = []data = "7,#,-3,#,#"return = ["#","[7,null,-3]"]The empty tree is written as a single #. The string data describes a different tree: 7 with an empty left child and a right child -3 that has two empty children. In level order that is [7,null,-3]; the two empty children of -3 come last, so they are removed.
Constraints
roothas from0to1000nodes.- Every node value in
rootis between-1000and1000. 1 <= data.length <= 10^4datais a valid encoding, in the format above, of a tree with0to1000nodes and values between-1000and1000. Values have no plus sign and no extra leading zeros.- Both trees (
rootand the tree thatdatadescribes) are at most500levels tall: no path from the root down to a leaf has more than500nodes.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- N-Ary Tree Codec OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions
- N-Ary Tree BFS CodecGoogle · ONSITE INTERVIEWGoogle interview questions
- Spreadsheet Formula DependenciesAmazon Web Services · ONSITE INTERVIEWAmazon Web Services interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Word Dictionary with Wildcard FindAmazon · ONSITE INTERVIEW
- Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
- Nested Todo ListNotion · PHONE SCREEN · ONSITE INTERVIEWNotion interview questions