297. Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree (LeetCode 297) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Serialization and Deserialization subpattern.

• Blind 75 · #35 of 75 · Trees
• NeetCode 150 · #60 of 150 · Trees
• NeetCode 250 · #110 of 250 · Trees

How to solve Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree is a Tree Serialization and Deserialization problem, part of Tree Traversal Patterns (DFS & BFS). Learn to serialize and deserialize binary trees. Convert trees to strings and reconstruct them.

Work towards the solution in these steps:

1. Consider how tree traversal techniques like DFS or BFS can help you systematically visit all nodes in the binary tree.
2. Think about representing null or absent children explicitly in your serialized string to preserve the tree structure.
3. Explore how preorder or level-order traversal sequences can be used to both serialize and deserialize the tree effectively.

The reference solution runs in O(n) time and O(n) space.

The Serialize and Deserialize Binary Tree solution and editorial walks through the full approach with reference code.

Problem statement

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

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

Example 2:

Input: root = [] Output: []

Constraints:

- The number of nodes in the tree is in the range [0, 104].

- -1000 <= Node.val <= 1000

Topics and companies

Topics: String, Tree, Depth-First Search, Breadth-First Search, Design, Binary Tree.

Reported in interviews at Facebook, Microsoft, Amazon, LinkedIn, Uber, Bloomberg, eBay, Quora, Qualtrics, Google, Oracle, Citadel and others.

How to practise Serialize and Deserialize Binary Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Serialize and Deserialize Binary Tree in the code editor, or read the Serialize and Deserialize Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where Serialize and Deserialize Binary Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Serialization and Deserialization subpattern
• The full DSA patterns sheet

Problems related to Serialize and Deserialize Binary Tree

Other problems that use the same Serialization and Deserialization and Tree Traversal Patterns (DFS & BFS) techniques:

• Find Duplicate Subtrees — Medium, same subpattern
• Subtree of Another Tree — Easy, same subpattern
• All Nodes Distance K in Binary Tree — Medium, same pattern
• Balanced Binary Tree — Easy, same pattern
• Binary Search Tree Iterator — Medium, same pattern
• Binary Tree Inorder Traversal — Easy, same pattern

Serialize and Deserialize Binary Tree FAQ