Meta — Serialize and Deserialize Binary Tree (BFS/Preorder)

Problem (Meta #1 Tree Problem)

Design an algorithm to serialize and deserialize a binary tree.

Example:

    1
   / \
  2   3
     / \
    4   5
Serialized: "1,2,null,null,3,4,null,null,5,null,null"

Solutions

Python — Preorder DFS

class Codec:
    def serialize(self, root) -> str:
        res = []
        def dfs(node):
            if not node:
                res.append('null')
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(res)

    def deserialize(self, data: str):
        vals = iter(data.split(','))
        def dfs():
            val = next(vals)
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

Python — BFS

from collections import deque

class Codec:
    def serialize(self, root) -> str:
        if not root: return ""
        q, res = deque([root]), []
        while q:
            node = q.popleft()
            if node:
                res.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
            else:
                res.append('null')
        return ','.join(res)

    def deserialize(self, data: str):
        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] != 'null':
                node.left = TreeNode(int(vals[i]))
                q.append(node.left)
            i += 1
            if vals[i] != 'null':
                node.right = TreeNode(int(vals[i]))
                q.append(node.right)
            i += 1
        return root

JavaScript

const serialize = (root) => {
    if (!root) return "";
    const q=[root], res=[];
    while(q.length){
        const n=q.shift();
        if(n){res.push(n.val);q.push(n.left,n.right);}
        else res.push('null');
    }
    return res.join(',');
};
const deserialize = (data) => {
    if(!data) return null;
    const v=data.split(','); const root={val:+v[0],left:null,right:null}; const q=[root]; let i=1;
    while(q.length){
        const n=q.shift();
        if(v[i]!=='null'){n.left={val:+v[i],left:null,right:null};q.push(n.left);}i++;
        if(v[i]!=='null'){n.right={val:+v[i],left:null,right:null};q.push(n.right);}i++;
    }
    return root;
};

Java

import java.util.*;
public String serialize(TreeNode root) {
    if (root==null) return "";
    StringBuilder sb=new StringBuilder(); Queue<TreeNode> q=new LinkedList<>(); q.offer(root);
    while (!q.isEmpty()) {
        TreeNode n=q.poll();
        if (n==null){sb.append("null,");continue;}
        sb.append(n.val).append(','); q.offer(n.left); q.offer(n.right);
    }
    return sb.toString();
}
public TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    String[] v=data.split(","); TreeNode root=new TreeNode(Integer.parseInt(v[0]));
    Queue<TreeNode> q=new LinkedList<>(); q.offer(root); int i=1;
    while (!q.isEmpty()) {
        TreeNode n=q.poll();
        if (!v[i].equals("null")){n.left=new TreeNode(Integer.parseInt(v[i]));q.offer(n.left);}i++;
        if (!v[i].equals("null")){n.right=new TreeNode(Integer.parseInt(v[i]));q.offer(n.right);}i++;
    }
    return root;
}

C++

#include <sstream>
#include <queue>
using namespace std;
string serialize(TreeNode* root) {
    if (!root) return "";
    queue<TreeNode*> q; q.push(root); string res;
    while (!q.empty()) {
        auto n=q.front(); q.pop();
        if (!n){res+="null,";continue;}
        res+=to_string(n->val)+','; q.push(n->left); q.push(n->right);
    }
    return res;
}
TreeNode* deserialize(string data) {
    if (data.empty()) return nullptr;
    istringstream ss(data); string tok; getline(ss,tok,',');
    TreeNode* root=new TreeNode(stoi(tok)); queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        auto n=q.front(); q.pop();
        getline(ss,tok,',');
        if (tok!="null"){n->left=new TreeNode(stoi(tok));q.push(n->left);}
        getline(ss,tok,',');
        if (tok!="null"){n->right=new TreeNode(stoi(tok));q.push(n->right);}
    }
    return root;
}

C

/* C: BFS with string building; tokenize on deserialize */