Serialize and Deserialize Binary Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Turn a binary tree into a string and rebuild the identical tree from that string.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Why is a plain preorder list of values not enough to rebuild a tree?
- Hint 2Add a special marker for every missing child.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Packing a family tree into a single line of text to send as a message. Write each person in order: person, then everything on their left branch, then everything on their right branch, and write "N" for every empty slot. Reading it back, you always know what comes next: take a person, then rebuild their left branch until the Ns tell you it has ended, then their right branch.
- The obvious way
Save both the preorder and inorder lists: works for distinct values but needs two lists and distinct values.
- The key insight
Serialize: visit in preorder; write the value for a real node and N for an empty spot, separated by commas. Deserialize: read the tokens in the same order with a pointer. An N means "no node here"; a number means "make a node, then build its left subtree from the next tokens, then its right subtree". The same recursion that wrote the string reads it.
- The algorithm
- serialize: at a node write its value, then serialize the left child, then the right child; at an empty spot write N.
- Join all pieces with commas.
- deserialize: split by commas and read from the front with one shared pointer.
- N: return nothing. A number: make the node, build its left, then its right.
Watch it run
Exampletree = [1, 2, 3, null, null, 4, 5]
Write 1. Its left child 2 has no children: write 2, N, N.
text: 1,2,N,N
Where people slip
- Always write the null marker; without it two different trees can give the same string.
- Level-order (BFS) serialization also works and matches how LeetCode prints trees.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class Codec:
def serialize(self, root):
parts = []
def write(node):
if node is None:
parts.append("N") # marker for an empty spot
return
parts.append(str(node.val))
write(node.left)
write(node.right)
write(root)
return ",".join(parts)
def deserialize(self, data):
tokens = iter(data.split(","))
def read():
token = next(tokens)
if token == "N":
return None
node = TreeNode(int(token))
node.left = read() # the same order we wrote in
node.right = read()
return node
return read()Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.