Serializing and Deserializing Binary Tree

Prereq: DFS on Tree

Given a binary tree, write a serialize function that converts the tree into a string and a deserialize function that converts a string to a binary tree. You may serialize the tree into any string representation you want as long as it can be deseralized.

Try it yourself

Explanation

To serialize, we can simply do a DFS and append the node value to the string. We need to encode null nodes too since otherwise, we wouldn't be able to tell if we have reached leaf nodes when we deserialize. We use x here as a placeholder for the null node.

To deserialize, we split the string into tokens and consume them. For each token we create a new node using the token value. When we see an x, we know we reached the leaf and return.

Serialize

Deserialize

1class Node:
2    def __init__(self, val, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def serialize(root):
8    res = []
9    def dfs(root):
10        if not root:
11            res.append('x')
12            return
13        res.append(root.val)
14        dfs(root.left)
15        dfs(root.right)
16    dfs(root)
17    return ' '.join(res)
18
19def deserialize(s):
20    def dfs(nodes):
21        val = next(nodes)
22        if val == 'x': return
23        cur = Node(int(val))
24        cur.left = dfs(nodes)
25        cur.right = dfs(nodes)
26        return cur
27    # create an iterator that returns a token each time we call `next`
28    return dfs(iter(s.split()))
29
30if __name__ == '__main__':
31    def build_tree(nodes):
32        val = next(nodes)
33        if not val or val == 'x': return
34        cur = Node(val)
35        cur.left = build_tree(nodes)
36        cur.right = build_tree(nodes)
37        return cur
38    def print_tree(root):
39        if not root:
40            yield "x"
41            return
42        yield str(root.val)
43        yield from print_tree(root.left)
44        yield from print_tree(root.right)
45    root = build_tree(iter(input().split()))
46    new_root = deserialize(serialize(root))
47    print(' '.join(print_tree(new_root)))
48

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Iterator;
4import java.util.List;
5import java.util.Scanner;
6import java.util.StringJoiner;
7
8class Solution {
9    public static String serialize(Node root) {
10        StringJoiner res = new StringJoiner(" ");
11        serializeDFS(root, res);
12        return res.toString();
13    }
14
15    private static void serializeDFS(Node root, StringJoiner result) {
16        if (root == null) {
17            result.add("x");
18            return;
19        }
20        result.add(Integer.toString(root.val));
21        serializeDFS(root.left, result);
22        serializeDFS(root.right, result);
23    }
24
25    public static Node deserialize(String root) {
26        // create an iterator that returns a token each time we call `next`
27        return deserializeDFS(Arrays.stream(root.split(" ")).iterator());
28    }
29
30    private static Node deserializeDFS(Iterator<String> nodes) {
31        String val = nodes.next();
32        if (val.equals("x")) return null;
33        Node cur = new Node(Integer.parseInt(val));
34        cur.left = deserializeDFS(nodes);
35        cur.right = deserializeDFS(nodes);
36        return cur;
37    }
38
39    /** Driver class, do not change **/
40    static class Node {
41        int val;
42        Node left, right;
43
44        public Node(int val) {
45            this.val = val;
46        }
47
48        public static Node buildTree(Iterator<String> iter) {
49            String nxt = iter.next();
50            if (nxt.equals("x")) return null;
51            Node node = new Node(Integer.parseInt(nxt));
52            node.left = buildTree(iter);
53            node.right = buildTree(iter);
54            return node;
55        }
56
57        public static void printTree(Node root, List<String> out) {
58            if (root == null) {
59                out.add("x");
60            } else {
61                out.add(String.valueOf(root.val));
62                printTree(root.left, out);
63                printTree(root.right, out);
64            }
65        }
66    }
67
68    public static void main(String[] args) {
69        Scanner scanner = new Scanner(System.in);
70        Node root = Node.buildTree(Arrays.stream(scanner.nextLine().split(" ")).iterator());
71        scanner.close();
72        Node newRoot = deserialize(serialize(root));
73        ArrayList<String> out = new ArrayList<>();
74        Node.printTree(newRoot, out);
75        System.out.println(String.join(" ", out));
76    }
77}
78

1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7    public class Node<T> {
8        public T val;
9        public Node<T> left;
10        public Node<T> right;
11
12        public Node(T val) {
13            this.val = val;
14        }
15
16        public Node(T val, Node<T> left, Node<T> right) {
17            this.val = val;
18            this.left = left;
19            this.right = right;
20        }
21    }
22
23    public static string Serialize(Node<int> root) {
24        List<string> res = new List<string>();
25        SerializeDFS(root, res);
26        return string.Join(" ", res);
27    }
28
29    private static void SerializeDFS(Node<int> root, List<string> result) {
30        if (root == null) {
31            result.Add("x");
32            return;
33        }
34        result.Add(root.val.ToString());
35        SerializeDFS(root.left, result);
36        SerializeDFS(root.right, result);
37    }
38
39    public static Node<int> Deserialize(string root) {
40        int pos = 0;
41        return DeserializeDFS(root.Split(" ").ToList(), ref pos);
42    }
43
44    private static Node<int> DeserializeDFS(List<string> nodes, ref int pos) {
45        string val = nodes[pos];
46        pos++;
47        if (val == "x") return null;
48        Node<int> cur = new Node<int>(int.Parse(val));
49        cur.left = DeserializeDFS(nodes, ref pos);
50        cur.right = DeserializeDFS(nodes, ref pos);
51        return cur;
52    }
53
54    public static Node<T> BuildTree<T>(List<string> strs, ref int pos, Func<string, T> f) {
55        string val = strs[pos];
56        pos++;
57        if (val == "x") return null;
58        Node<T> left = BuildTree<T>(strs, ref pos, f);
59        Node<T> right = BuildTree<T>(strs, ref pos, f);
60        return new Node<T>(f(val), left, right);
61    }
62
63    public static void PrintTree<T>(Node<T> root, List<string> tree) {
64        if (root == null) {
65            tree.Add("x");
66        } else {
67            tree.Add(root.val.ToString());
68            PrintTree(root.left, tree);
69            PrintTree(root.right, tree);
70        }
71    }
72
73    public static List<string> SplitWords(string s) {
74        return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
75    }
76
77    public static void Main()
78    {
79        List<string> strs = SplitWords(Console.ReadLine());
80        int pos = 0;
81        Node<int> root = BuildTree(strs, ref pos, int.Parse);
82        Node<int> newRoot = Deserialize(Serialize(root));
83        List<string> tree = new List<string>();
84        PrintTree(newRoot, tree);
85        Console.WriteLine(string.Join(" ", tree));
86    }
87}
88

1class Node {
2    constructor(val, left = null, right = null) {
3        this.val = val;
4        this.left = left;
5        this.right = right;
6    }
7}
8
9function serialize(root) {
10    let res = [];
11    serialize_dfs(root, res);
12    return res.join(" ");
13}
14
15function serialize_dfs(root, res) {
16    if (!root) {
17        res.push("x");
18        return;
19    }
20    res.push(root.val);
21    serialize_dfs(root.left, res);
22    serialize_dfs(root.right, res);
23}
24
25function deserialize(s) {
26    // create an iterator that returns a token each time we call `next`
27    return deserialize_dfs(s.split(" ")[Symbol.iterator]());
28}
29
30function deserialize_dfs(nodes) {
31    let val = nodes.next().value;
32    if (val === 'x') return;
33    const cur = new Node(parseInt(val, 10));
34    cur.left = deserialize_dfs(nodes);
35    cur.right = deserialize_dfs(nodes);
36    return cur;
37}
38
39function buildTree(nodes, f) {
40    const val = nodes.next().value;
41    if (val === 'x') return null;
42    const left = buildTree(nodes, f);
43    const right = buildTree(nodes, f);
44    return new Node(f(val), left, right);
45}
46
47function* print_tree(root) {
48    if (!root) {
49        yield "x";
50    } else {
51        yield root.val;
52        yield* print_tree(root.left);
53        yield* print_tree(root.right);
54    }
55}
56
57function splitWords(s) {
58    return s == "" ? [] : s.split(' ');
59}
60
61function* main() {
62    const root = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
63    const new_root = deserialize(serialize(root));
64    console.log(Array.from(print_tree(new_root)).join(' '));
65}
66
67class EOFError extends Error {}
68{
69    const gen = main();
70    const next = (line) => gen.next(line).done && process.exit();
71    let buf = '';
72    next();
73    process.stdin.setEncoding('utf8');
74    process.stdin.on('data', (data) => {
75        const lines = (buf + data).split('\n');
76        buf = lines.pop();
77        lines.forEach(next);
78    });
79    process.stdin.on('end', () => {
80        buf && next(buf);
81        gen.throw(new EOFError());
82    });
83}
84

1#include <algorithm> // copy
2#include <iostream> // cin, cout
3#include <iterator> // back_inserter, istream_iterator, ostream_iterator, prev
4#include <sstream> // istringstream
5#include <string> // getline, stoi, string, to_string
6#include <vector> // vector
7
8template <typename T>
9struct Node {
10    T val;
11    Node<T>* left;
12    Node<T>* right;
13
14    explicit Node(T val, Node<T>* left = nullptr, Node<T>* right = nullptr)
15        : val{val}, left{left}, right{right} {}
16
17    ~Node() {
18        delete left;
19        delete right;
20    }
21};
22
23void serialize_dfs(Node<int>* root, std::vector<std::string>& res) {
24    if (root == nullptr) {
25        res.emplace_back("x");
26        return;
27    }
28    res.emplace_back(std::to_string(root->val));
29    serialize_dfs(root->left, res);
30    serialize_dfs(root->right, res);
31}
32
33std::string serialize(Node<int>* root) {
34    std::vector<std::string> res;
35    serialize_dfs(root, res);
36    std::stringstream ss;
37    std::copy(res.begin(), res.end(), std::ostream_iterator<std::string>(ss, " "));
38    return ss.str();
39}
40
41Node<int>* deserialize_dfs(std::vector<std::string>::iterator& nodes) {
42    std::string val = *nodes;
43    ++nodes;
44    if (val == "x") return nullptr;
45    Node<int>* cur = new Node<int>(std::stoi(val));
46    cur->left = deserialize_dfs(nodes);
47    cur->right = deserialize_dfs(nodes);
48    return cur;
49}
50
51Node<int>* deserialize(std::string root) {
52    std::istringstream ss(root);
53    std::vector<std::string> nodes;
54    std::copy(std::istream_iterator<std::string>(ss), std::istream_iterator<std::string>(), std::back_inserter(nodes));
55    auto nodes_iter = nodes.begin();
56
57    return deserialize_dfs(nodes_iter);
58}
59
60template<typename T, typename Iter, typename F>
61Node<T>* build_tree(Iter& it, F f) {
62    std::string val = *it;
63    ++it;
64    if (val == "x") return nullptr;
65    Node<T>* left = build_tree<T>(it, f);
66    Node<T>* right = build_tree<T>(it, f);
67    return new Node<T>{f(val), left, right};
68}
69
70template<typename T, typename F>
71void format_tree(Node<T>* node, F f, std::vector<std::string>& out) {
72    if (node == nullptr) {
73        out.emplace_back("x");
74        return;
75    }
76    out.emplace_back(f(node->val));
77    format_tree(node->left, f, out);
78    format_tree(node->right, f, out);
79}
80
81template<typename T>
82std::vector<T> get_words() {
83    std::string line;
84    std::getline(std::cin, line);
85    std::istringstream ss{line};
86    std::vector<T> v;
87    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
88    return v;
89}
90
91template<typename T>
92void put_words(const std::vector<T>& v) {
93    if (!v.empty()) {
94        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
95        std::cout << v.back();
96    }
97    std::cout << '\n';
98}
99
100int main() {
101    std::vector<std::string> tree_vec = get_words<std::string>();
102    auto tree_it = tree_vec.begin();
103    Node<int>* tree = build_tree<int>(tree_it, [](auto s) { return std::stoi(s); });
104    Node<int>* res = deserialize(serialize(tree));
105    std::vector<std::string> res_vec;
106    format_tree(res, [](auto v) { return std::to_string(v); }, res_vec);
107    put_words(res_vec);
108}
109

Time Complexity: O(n) to traverse n nodes/elements

Space Complexity:

serialize - O(h) stack memory where h is the height of the tree, which is worst case O(n)
deserialize - O(h) stack memory (worst case O(n)) and O(n) new nodes, O(n) dominates the space complexity

Still not clear? Submit the part you don't understand to our editors.

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Knapsack

Coin Change

Grid

Dynamic number of subproblems

Interval

Two Sequences

0-1 Knapsack

Bitmask

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

Serializing and Deserializing Binary Tree

Try it yourself

Explanation