Serialize and Deserialize Binary Search Tree (BST) Editorial

Practice Problem Link: Serialize And Deserialize Binary Search Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Serialization is the process of translating a data structure or object state into a format that can be stored (for example, in a file or memory data buffer) or transmitted (for example, over a computer network) and reconstructed later (possibly in a different computer environment).

The opposite operation, extracting a data structure from a series of bytes, is deserialization.

Design an algorithm to serialize and deserialize a BST.

• The serialize method should return a string. The format of the string does not matter. Try to keep it as compact as possible to avoid getting TLE/MLE.
• The deserialize method when provided the serialized string should return the original BST.

Approach

The given BST can be stored in a preorder or postorder traversal way in a string. Each node can be separated by a special character say (" ") and the NULL nodes can be stored as another special character say ("#").

To get back the original BST, pick up every substring that is separated by (" "), convert it to its corresponding value and add it to the BST. Do this recursively for the children nodes in the same order in which the string was serialized.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

string serialize(Node* root) {
	if (root == NULL) {
        return "#";
	}
    string left = serialize(root->left);
    string right = serialize(root->right);
    return to_string(root->data) + " " + left + " " + right;
}

Node* helper(stringstream &treeNodes) {
	string currNode = "";
    treeNodes >> currNode;
    if (currNode == "#") {
		return NULL;
	}
    Node* newNode = new Node(stoi(currNode));
    newNode->left = helper(treeNodes);
    newNode->right = helper(treeNodes);
    return newNode;
}

Node* deserialize(string serializedTree) {
    stringstream treeNodes(serializedTree);
    return helper(treeNodes);
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/

	String serialize(Node root) {
        if (root == null) {
            return "#";
		}
        String left = serialize(root.left);
        String right = serialize(root.right);
        StringBuilder sb = new StringBuilder();
        sb.append(root.data).append(" ").append(left).append(" ").append(right);
        return sb.toString();
	}

	public Node helper(Queue<String> treeNodes) {
        String currNode = treeNodes.poll();
        if (currNode.equals("#")) {
			return null;
		}
        Node newNode = new Node(Integer.valueOf(currNode));
        newNode.left = helper(treeNodes);
        newNode.right = helper(treeNodes);
        return newNode;
    }
	
	Node deserialize(String serializedString) {
        Queue<String> treeNodes = new LinkedList<String>();
        treeNodes.addAll(Arrays.asList(serializedString.split(" ")));
        return helper(treeNodes);
    }

}