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 token value. When we see an x we know we reached the leaf and return.

Serialize

Deserialize

Expand 4 lines ...
        self.right = right

def serialize(root):
    # WRITE YOUR BRILLIANT CODE HERE
    res = []
    def dfs(root):
        if not root:
            res.append('x')
            return
        res.append(root.val)
        dfs(root.left)
        dfs(root.right)
    dfs(root)
    return ' '.join(res)

def deserialize(s):
    # AND HERE
    def dfs(nodes):
        val = next(nodes)
        if val == 'x': return
        cur = Node(int(val))
        cur.left = dfs(nodes)
        cur.right = dfs(nodes)
        return cur
    # create an iterator that returns a token each time we call `next`
    return dfs(iter(s.split()))

if __name__ =="__main__":
    # driver code, do not modify
    def build_tree(nodes):
        val = next(nodes)
        if not val or val == 'x': return
Expand 14 lines ...

Expand 2 lines ...
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.StringJoiner;
class Solution {

    public static String serialize(Node root) {
        // WRITE YOUR BRILLIANT CODE HERE
        StringJoiner res = new StringJoiner(" ");
        serializeDFS(root, res);
        return res.toString();
    }

    private static void serializeDFS(Node root, StringJoiner result) {
        if (root == null) {
            result.add("x");
            return;
        }
        result.add(Integer.toString(root.val));
        serializeDFS(root.left, result);
        serializeDFS(root.right, result);
    }

    public static Node deserialize(String root) {
        // AND HERE
        // create an iterator that returns a token each time we call `next`
        return deserializeDFS(Arrays.stream(root.split(" ")).iterator());
    }

    private static Node deserializeDFS(Iterator<String> nodes) {
        String val = nodes.next();
        if (val.equals("x")) return null;
        Node cur = new Node(Integer.parseInt(val));
        cur.left = deserializeDFS(nodes);
        cur.right = deserializeDFS(nodes);
        return cur;
    }

    /** Driver class, do not change **/
    static class Node {
        int val;
        Node left, right;

Expand 35 lines ...

Expand 8 lines ...
}

function serialize(root) {
    // WRITE YOUR BRILLIANT CODE HERE
    let res = [];
    serialize_dfs(root, res);
    return res.join(" ");
}

function serialize_dfs(root, res) {
    if (!root) {
        res.push("x");
        return;
    }
    res.push(root.val);
    serialize_dfs(root.left, res);
    serialize_dfs(root.right, res);
}

function deserialize(s) {
    // AND HERE
    // create an iterator that returns a token each time we call `next`
    return deserialize_dfs(s.split(" ")[Symbol.iterator]());
}

function deserialize_dfs(nodes) {
    let val = nodes.next().value;
    if (val === 'x') return;
    const cur = new Node(parseInt(val, 10));
    cur.left = deserialize_dfs(nodes);
    cur.right = deserialize_dfs(nodes);
    return cur;
}

function build_tree(nodes) {
    let val = nodes.next().value;
    if (!val || val === 'x') return;
    let cur = new Node(parseInt(val, 10));
    cur.left = build_tree(nodes);
Expand 23 lines ...

			Expand 4 lines ...
5	5		`self.right = right`
6	6
7	7		`def serialize(root):`
8		-	`# WRITE YOUR BRILLIANT CODE HERE`
	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	+
9	19		`def deserialize(s):`
10		-	`# AND HERE`
	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	+
11	30		`if __name__ =="__main__":`
12	31		`# driver code, do not modify`
13	32		`def build_tree(nodes):`
14	33		`val = next(nodes)`
15	34		`if not val or val == 'x': return`
			Expand 14 lines ...

			Expand 2 lines ...
3	3		`import java.util.Iterator;`
4	4		`import java.util.List;`
5	5		`import java.util.Scanner;`
	6	+	`import java.util.StringJoiner;`
6	7		`class Solution {`
7	8
8	9		`public static String serialize(Node root) {`
9		-	`// WRITE YOUR BRILLIANT CODE HERE`
	10	+	`StringJoiner res = new StringJoiner(" ");`
	11	+	`serializeDFS(root, res);`
	12	+	`return res.toString();`
10	13		`}`
11	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	+
12	25		`public static Node deserialize(String root) {`
13		-	`// AND HERE`
	26	+	// create an iterator that returns a token each time we call `next`
	27	+	`return deserializeDFS(Arrays.stream(root.split(" ")).iterator());`
14	28		`}`
15	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	+
16	39		`/ Driver class, do not change /`
17	40		`static class Node {`
18	41		`int val;`
19	42		`Node left, right;`
20	43
			Expand 35 lines ...

			Expand 8 lines ...
9	9		`}`
10	10
11	11		`function serialize(root) {`
12		-	`// WRITE YOUR BRILLIANT CODE HERE`
	12	+	`let res = [];`
	13	+	`serialize_dfs(root, res);`
	14	+	`return res.join(" ");`
13	15		`}`
14	16
	17	+	`function serialize_dfs(root, res) {`
	18	+	`if (!root) {`
	19	+	`res.push("x");`
	20	+	`return;`
	21	+	`}`
	22	+	`res.push(root.val);`
	23	+	`serialize_dfs(root.left, res);`
	24	+	`serialize_dfs(root.right, res);`
	25	+	`}`
	26	+
15	27		`function deserialize(s) {`
16		-	`// AND HERE`
	28	+	// create an iterator that returns a token each time we call `next`
	29	+	`return deserialize_dfs(s.split(" ")[Symbol.iterator]());`
17	30		`}`
18	31
	32	+	`function deserialize_dfs(nodes) {`
	33	+	`let val = nodes.next().value;`
	34	+	`if (val === 'x') return;`
	35	+	`const cur = new Node(parseInt(val, 10));`
	36	+	`cur.left = deserialize_dfs(nodes);`
	37	+	`cur.right = deserialize_dfs(nodes);`
	38	+	`return cur;`
	39	+	`}`
	40	+
19	41		`function build_tree(nodes) {`
20	42		`let val = nodes.next().value;`
21	43		`if (!val \|\| val === 'x') return;`
22	44		`let cur = new Node(parseInt(val, 10));`
23	45		`cur.left = build_tree(nodes);`
			Expand 23 lines ...

Your Progress

Getting Started

Overview

Basic Data Structures

Binary Search

Overview

Sorted Array

Implicitly Sorted Array

Depth First Search

Introduction

DFS on Tree

Backtracking

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Breadth First Search

Introduction

BFS on Tree

Graph

Introduction

BFS

Matrix as Graph

Directed Graph

Two Pointers

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Priority Queue / Heap

Introduction

Top K

Advanced

Divide and Conquer

Introduction

Generalized

Binary Search

Dynamic Programming

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Two Sequences

Game Theory

Other

Monotonic Stack

Interval

Data Structure Design

Amazon Online Assessment Questions (OA)

OA2 2021/2020

OA2 2020 and earlier

OA1

Microsoft Online Assessment Questions 2021 (OA)

Microsoft OA

Serializing and Deserializing Binary Tree

Try it yourself

Explanation