Serializing and Deserializing Binary Tree

Prerequisite: 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 back to a binary tree. You may serialize the tree into any string representation you want, as long as it can be deserialized properly.

Try it yourself

Explanation

The serialize function takes the root of a binary tree and turns it into a string representation. The nodes are traversed in depth first search (DFS) order (visiting a node, then its left child, then its right child). To serialize the root of the current binary tree, we'll first append the value at each node to the string, with 'x' appended for null nodes ,then add the serialization for the subtrees at the left and right children (in that order since this is a DFS) by using the serialize function. The 'x' is used to allow us to differentiate leaf nodes from non-leaf nodes when deserializing. This final string is then returned by the serialize function.

To deserialize, we take a string representation of a binary tree and rebuild the original tree. We can accomplish this by splitting the string into tokens and reading them in the original DFS order. If it encounters a node value, it instantiates a new node with the same value. If it encounters an 'x', it interprets this as a leaf node (null).

Serialize

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide

Deserialize

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
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
10    def dfs(root):
11        if not root:
12            res.append("x")
13            return
14        res.append(root.val)
15        dfs(root.left)
16        dfs(root.right)
17
18    dfs(root)
19    return " ".join(res)
20
21def deserialize(s):
22    def dfs(nodes):
23        val = next(nodes)
24        if val == "x":
25            return None
26        cur = Node(int(val))
27        cur.left = dfs(nodes)
28        cur.right = dfs(nodes)
29        return cur
30
31    # create an iterator that returns a token each time we call `next`
32    return dfs(iter(s.split()))
33
34if __name__ == "__main__":
35    def build_tree(nodes):
36        val = next(nodes)
37        if not val or val == "x":
38            return None
39        cur = Node(val)
40        cur.left = build_tree(nodes)
41        cur.right = build_tree(nodes)
42        return cur
43
44    def print_tree(root):
45        if not root:
46            yield "x"
47            return
48        yield str(root.val)
49        yield from print_tree(root.left)
50        yield from print_tree(root.right)
51
52    root = build_tree(iter(input().split()))
53    new_root = deserialize(serialize(root))
54    print(" ".join(print_tree(new_root)))
55
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    /**
40     * Driver class, do not change
41     */
42    static class Node {
43        int val;
44        Node left, right;
45
46        public Node(int val) {
47            this.val = val;
48        }
49
50        public static Node buildTree(Iterator<String> iter) {
51            String nxt = iter.next();
52            if (nxt.equals("x")) return null;
53            Node node = new Node(Integer.parseInt(nxt));
54            node.left = buildTree(iter);
55            node.right = buildTree(iter);
56            return node;
57        }
58
59        public static void printTree(Node root, List<String> out) {
60            if (root == null) {
61                out.add("x");
62            } else {
63                out.add(String.valueOf(root.val));
64                printTree(root.left, out);
65                printTree(root.right, out);
66            }
67        }
68    }
69
70    public static void main(String[] args) {
71        Scanner scanner = new Scanner(System.in);
72        Node root = Node.buildTree(Arrays.stream(scanner.nextLine().split(" ")).iterator());
73        scanner.close();
74        Node newRoot = deserialize(serialize(root));
75        ArrayList<String> out = new ArrayList<>();
76        Node.printTree(newRoot, out);
77        System.out.println(String.join(" ", out));
78    }
79}
80
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7    public class Node<T>
8    {
9        public T val;
10        public Node<T> left;
11        public Node<T> right;
12
13        public Node(T val)
14        {
15            this.val = val;
16        }
17
18        public Node(T val, Node<T> left, Node<T> right)
19        {
20            this.val = val;
21            this.left = left;
22            this.right = right;
23        }
24    }
25
26    public static string Serialize(Node<int> root)
27    {
28        List<string> res = new List<string>();
29        SerializeDFS(root, res);
30        return string.Join(" ", res);
31    }
32
33    private static void SerializeDFS(Node<int> root, List<string> result)
34    {
35        if (root == null)
36        {
37            result.Add("x");
38            return;
39        }
40        result.Add(root.val.ToString());
41        SerializeDFS(root.left, result);
42        SerializeDFS(root.right, result);
43    }
44
45    public static Node<int> Deserialize(string root)
46    {
47        int pos = 0;
48        return DeserializeDFS(root.Split(" ").ToList(), ref pos);
49    }
50
51    private static Node<int> DeserializeDFS(List<string> nodes, ref int pos)
52    {
53        string val = nodes[pos];
54        pos++;
55        if (val == "x") return null;
56        Node<int> cur = new Node<int>(int.Parse(val));
57        cur.left = DeserializeDFS(nodes, ref pos);
58        cur.right = DeserializeDFS(nodes, ref pos);
59        return cur;
60    }
61
62    public static Node<T> BuildTree<T>(List<string> strs, ref int pos, Func<string, T> f)
63    {
64        string val = strs[pos];
65        pos++;
66        if (val == "x") return null;
67        Node<T> left = BuildTree<T>(strs, ref pos, f);
68        Node<T> right = BuildTree<T>(strs, ref pos, f);
69        return new Node<T>(f(val), left, right);
70    }
71
72    public static void PrintTree<T>(Node<T> root, List<string> tree)
73    {
74        if (root == null)
75        {
76            tree.Add("x");
77        }
78        else
79        {
80            tree.Add(root.val.ToString());
81            PrintTree(root.left, tree);
82            PrintTree(root.right, tree);
83        }
84    }
85
86    public static List<string> SplitWords(string s)
87    {
88        return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
89    }
90
91    public static void Main()
92    {
93        List<string> strs = SplitWords(Console.ReadLine());
94        int pos = 0;
95        Node<int> root = BuildTree(strs, ref pos, int.Parse);
96        Node<int> newRoot = Deserialize(Serialize(root));
97        List<string> tree = new List<string>();
98        PrintTree(newRoot, tree);
99        Console.WriteLine(string.Join(" ", tree));
100    }
101}
102
1"use strict";
2
3class Node {
4    constructor(val, left = null, right = null) {
5        this.val = val;
6        this.left = left;
7        this.right = right;
8    }
9}
10
11function serializeDFS(root, res) {
12    if (!root) {
13        res.push("x");
14        return;
15    }
16    res.push(root.val);
17    serializeDFS(root.left, res);
18    serializeDFS(root.right, res);
19}
20
21function serialize(root) {
22    const res = [];
23    serializeDFS(root, res);
24    return res.join(" ");
25}
26
27function deserializeDFS(nodes) {
28    const val = nodes.next().value;
29    if (val === "x") return null;
30    const cur = new Node(parseInt(val, 10));
31    cur.left = deserializeDFS(nodes);
32    cur.right = deserializeDFS(nodes);
33    return cur;
34}
35
36function deserialize(s) {
37    // create an iterator that returns a token each time we call `next`
38    return deserializeDFS(s.split(" ")[Symbol.iterator]());
39}
40
41function buildTree(nodes, f) {
42    const val = nodes.next().value;
43    if (val === "x") return null;
44    const left = buildTree(nodes, f);
45    const right = buildTree(nodes, f);
46    return new Node(f(val), left, right);
47}
48
49function* printTree(root) {
50    if (!root) {
51        yield "x";
52    } else {
53        yield root.val;
54        yield* printTree(root.left);
55        yield* printTree(root.right);
56    }
57}
58
59function splitWords(s) {
60    return s === "" ? [] : s.split(" ");
61}
62
63function* main() {
64    const root = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
65    const newRoot = deserialize(serialize(root));
66    console.log(Array.from(printTree(newRoot)).join(" "));
67}
68
69class EOFError extends Error {}
70{
71    const gen = main();
72    const next = (line) => gen.next(line).done && process.exit();
73    let buf = "";
74    next();
75    process.stdin.setEncoding("utf8");
76    process.stdin.on("data", (data) => {
77        const lines = (buf + data).split("\n");
78        buf = lines.pop();
79        lines.forEach(next);
80    });
81    process.stdin.on("end", () => {
82        buf && next(buf);
83        gen.throw(new EOFError());
84    });
85}
86
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <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    auto* 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(const 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
1package main
2
3import (
4    "bufio"
5    "fmt"
6    "os"
7    "strconv"
8    "strings"
9)
10
11type Node struct {
12    val   int
13    left  *Node
14    right *Node
15}
16
17func serialize(root *Node) string {
18    var res []string
19    var dfs func(*Node)
20    dfs = func(root *Node) {
21        if root == nil {
22            res = append(res, "x")
23            return
24        }
25        res = append(res, strconv.Itoa(root.val))
26        dfs(root.left)
27        dfs(root.right)
28    }
29    dfs(root)
30    return strings.Join(res, " ")
31}
32
33func deserialize(s string) *Node {
34    nodes := strings.Fields(s)
35    var index int
36    var dfs func() *Node
37    dfs = func() *Node {
38        val := nodes[index]
39        index++
40        if val == "x" {
41            return nil
42        }
43        num, err := strconv.Atoi(val)
44        if err != nil {
45            panic(err)
46        }
47        cur := &Node{val: num}
48        cur.left = dfs()
49        cur.right = dfs()
50        return cur
51    }
52
53    return dfs()
54}
55
56func buildTree(nodes []string, pos *int) *Node {
57    val := nodes[*pos]
58    *pos++
59    if val == "x" {
60        return nil
61    }
62    v, _ := strconv.Atoi(val)
63    left := buildTree(nodes, pos)
64    right := buildTree(nodes, pos)
65    return &Node{v, left, right}
66}
67
68func splitWords(s string) []string {
69    if s == "" {
70        return []string{}
71    }
72    return strings.Split(s, " ")
73}
74
75func formatTree(node *Node, out []string) []string {
76    if node == nil {
77        out = append(out, "x")
78    } else {
79        out = append(out, strconv.Itoa(node.val))
80        out = formatTree(node.left, out)
81        out = formatTree(node.right, out)
82    }
83    return out
84}
85
86func main() {
87    scanner := bufio.NewScanner(os.Stdin)
88    scanner.Scan()
89    bstIdx := 0
90    root := buildTree(splitWords(scanner.Text()), &bstIdx)
91    res := deserialize(serialize(root))
92    out := make([]string, 0)
93    out = formatTree(res, out)
94    fmt.Println(strings.Join(out, " "))
95}
96

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
Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro
Favorite (idle)