Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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:
[0, 104].-1000 <= Node.val <= 1000Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree · Design
[1,2,3,null,null,4,5]
[]
encode-and-decode-strings)serialize-and-deserialize-bst)find-duplicate-subtrees)serialize-and-deserialize-n-ary-tree)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #297: Serialize and Deserialize Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
List<String> ans = new ArrayList<>();
Deque<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node != null) {
ans.add(node.val + "");
q.offer(node.left);
q.offer(node.right);
} else {
ans.add("#");
}
}
return String.join(",", ans);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) {
return null;
}
String[] vals = data.split(",");
int i = 0;
TreeNode root = new TreeNode(Integer.valueOf(vals[i++]));
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (!"#".equals(vals[i])) {
node.left = new TreeNode(Integer.valueOf(vals[i]));
q.offer(node.left);
}
++i;
if (!"#".equals(vals[i])) {
node.right = new TreeNode(Integer.valueOf(vals[i]));
q.offer(node.right);
}
++i;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
// Accepted solution for LeetCode #297: Serialize and Deserialize Binary Tree
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return ""
}
q := []*TreeNode{root}
ans := []string{}
for len(q) > 0 {
node := q[0]
q = q[1:]
if node != nil {
ans = append(ans, strconv.Itoa(node.Val))
q = append(q, node.Left)
q = append(q, node.Right)
} else {
ans = append(ans, "#")
}
}
return strings.Join(ans, ",")
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
if data == "" {
return nil
}
vals := strings.Split(data, ",")
v, _ := strconv.Atoi(vals[0])
i := 1
root := &TreeNode{Val: v}
q := []*TreeNode{root}
for len(q) > 0 {
node := q[0]
q = q[1:]
if x, err := strconv.Atoi(vals[i]); err == nil {
node.Left = &TreeNode{Val: x}
q = append(q, node.Left)
}
i++
if x, err := strconv.Atoi(vals[i]); err == nil {
node.Right = &TreeNode{Val: x}
q = append(q, node.Right)
}
i++
}
return root
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/
# Accepted solution for LeetCode #297: Serialize and Deserialize Binary Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if root is None:
return ""
q = deque([root])
ans = []
while q:
node = q.popleft()
if node:
ans.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
ans.append("#")
return ",".join(ans)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
vals = data.split(",")
root = TreeNode(int(vals[0]))
q = deque([root])
i = 1
while q:
node = q.popleft()
if vals[i] != "#":
node.left = TreeNode(int(vals[i]))
q.append(node.left)
i += 1
if vals[i] != "#":
node.right = TreeNode(int(vals[i]))
q.append(node.right)
i += 1
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
// Accepted solution for LeetCode #297: Serialize and Deserialize Binary Tree
use rustgym_util::*;
use std::iter::Peekable;
use std::vec::IntoIter;
struct Codec;
enum Tok {
Op(char),
Num(i32),
}
impl Codec {
fn new() -> Self {
Codec {}
}
fn serialize(&self, root: TreeLink) -> String {
let mut res = "".to_string();
Self::serialize_tree(&root, &mut res);
res
}
fn serialize_tree(root: &TreeLink, s: &mut String) {
s.push('(');
if let Some(node) = root {
let node = node.borrow();
*s += &format!("{}", node.val);
Self::serialize_tree(&node.left, s);
Self::serialize_tree(&node.right, s);
}
s.push(')');
}
fn deserialize(&self, data: String) -> TreeLink {
let tokens = Self::parse_tokens(data);
let mut it = tokens.into_iter().peekable();
Self::parse_tree(&mut it)
}
fn parse_tokens(data: String) -> Vec<Tok> {
let mut it = data.chars().peekable();
let mut res = vec![];
while let Some(c) = it.next() {
if c == '(' || c == ')' {
res.push(Tok::Op(c));
} else {
let mut sign = 1;
let mut x = 0;
if c == '-' {
sign = -1;
} else {
x = (c as u8 - b'0') as i32;
}
while let Some('0'..='9') = it.peek() {
x *= 10;
x += (it.next().unwrap() as u8 - b'0') as i32;
}
res.push(Tok::Num(sign * x));
}
}
res
}
fn parse_tree(it: &mut Peekable<IntoIter<Tok>>) -> TreeLink {
let mut res = None;
it.next();
match it.peek() {
Some(&Tok::Num(x)) => {
it.next();
res = tree!(x, Self::parse_tree(it), Self::parse_tree(it))
}
Some(Tok::Op(')')) => {}
_ => panic!(),
}
it.next();
res
}
}
#[test]
fn test() {
let codec = Codec::new();
let root = tree!(1, tree!(2), tree!(3, tree!(4), tree!(5)));
let res = tree!(1, tree!(2), tree!(3, tree!(4), tree!(5)));
assert_eq!(codec.deserialize(codec.serialize(root)), res);
}
// Accepted solution for LeetCode #297: Serialize and Deserialize Binary Tree
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/*
* Encodes a tree to a single string.
*/
function serialize(root: TreeNode | null): string {
const box = [];
function cereal(root: TreeNode | null) {
if (root === null) return box.push(null);
box.push(root.val);
cereal(root.left);
cereal(root.right);
}
cereal(root);
return box.join(',');
}
/*
* Decodes your encoded data to tree.
*/
function deserialize(data: string): TreeNode | null {
const box: string[] = data.split(',');
function decereal(): TreeNode | null {
const val = box.shift();
if (val === '') return null;
const node = new TreeNode(Number(val));
node.left = decereal();
node.right = decereal();
return node;
}
return decereal();
}
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.