Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    vector<string> split(string s) {
        vector<string> split_str;
        stringstream ss(s);
        string tmp;
        while (getline(ss, tmp, ',')) {
            split_str.push_back(tmp);
        }
        return split_str;
    }

    // Encodes a tree to a single string.
    vector<string> serialize(TreeNode* root) {
        vector<string> serialized;
        string ans;
        if (root == NULL) {
            return serialized;
        }
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if (ans.empty()) {
                ans = to_string(node -> val);
            } else {
                ans += "," + (node != NULL ? to_string(node -> val) : "#");
            }
            if (node != NULL) {
                q.push(node -> left);
                q.push(node -> right);
            }
        }
        
        serialized = split(ans);
        int size = serialized.size() - 1;
        while (size >= 0) {
            if (serialized[size--] != "#") {
                break;
            }
            serialized.erase(serialized.begin() + size + 1);
        }
        return serialized; 
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(vector<string> data) {
        if (data.empty()) {
            return NULL;
        }
        TreeNode *root = new TreeNode(stoi(data[0]));
        int size = data.size(), i = 1;
        queue<TreeNode *> q;
        q.push(root);
        
        while (i < size && !q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if (data[i++] != "#") {
                node -> left = new TreeNode(stoi(data[i - 1]));
                q.push(node -> left);
            }
            if (data[i++] != "#") {
                node -> right = new TreeNode(stoi(data[i - 1]));
                q.push(node -> right);
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));


========== Another =========
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        if (root == NULL) {
            return ans;
        }
        vector<string> sol;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if (node != NULL) {
                sol.push_back(to_string(node -> val));
                q.push(node -> left);
                q.push(node -> right);
            } else {
                sol.push_back("null");
            }
        }
        
        formatResponse(ans, sol);
        return ans;
    }
    
    void formatResponse(string& ans, vector<string>& strList) {
        int size = strList.size();
        if (size == 0) {
            ans = "";
            return;
        }
        
        for (int i = size - 1; i >= 0; i--) {
            if (strList[i] == "null") {
                strList.pop_back();
            } else {
                break;
            }
        }
        
        for (int i = 0; i < strList.size(); i++) {
            if (i == 0) {
                ans += strList[i];
            } else {
                ans += "," + strList[i];
            }
        }
    }

    void split(string s, vector<string>& resp, char delim) {
        stringstream ss(s);
        string str;
        while(getline(ss, str, delim)) {
            resp.push_back(str);
        }
        return;
    }
    
    void helper(TreeNode *& root, vector<string>& input) {
        if (input.size() == 0 || input[0] == "null") {
            root = NULL;
            return;
        }
        
        root = new TreeNode(stoi(input[0]));
        queue<TreeNode *> q;
        q.push(root);
        int size = input.size();
        int iter = 1;
        while (1) {
            if (q.empty() || iter == size) {
                break;
            }
            TreeNode *node = q.front(); q.pop();
            if (input[iter] != "null") {
                node -> left = new TreeNode(stoi(input[iter]));
                q.push(node -> left);
            } else {
                node -> left = NULL;
            }
            iter++;
            if (iter == size) {
                break;
            }
            if (input[iter] != "null") {
                node -> right = new TreeNode(stoi(input[iter]));
                q.push(node -> right);
            } else {
                node -> right = NULL;
            }
            iter++;
        }
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode *root = NULL;
        if (data.empty()) {
            return root;
        }
        
        vector<string> input;
        split(data, input, ',');
        
        helper(root, input);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;

// codec.deserialize(codec.serialize(root));

========================

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Codec {

public:

    vector<string> split(string str) {

        stringstream ss(str);

        vector<string> ans;

        string tmp;

        while(getline(ss, tmp, ',')) {

            ans.push_back(tmp);

        }

        return ans;

    }

    // Encodes a tree to a single string.

    string serialize(TreeNode* root) {

        queue<TreeNode *> q;

        if (root == NULL) {

            return "";

        }

        string ans;

        q.push(root);

        while (!q.empty()) {

            TreeNode *node = q.front(); q.pop();

            string code;

            if (node != NULL) {

                code = to_string(node -> val);

            } else {

                code = "#";

            }

            ans += (ans != "" ? "," +  code: code);

            if (node == NULL) {

                continue;

            }

            q.push(node -> left);

            q.push(node -> right);

        }

        // Check if trimming needed in the last.

        return ans;

    }

    // Decodes your encoded data to tree.

    TreeNode* deserialize(string data) {

        if (data == "" || data == "#") {

            return NULL;

        }

        

        vector<string> str_list = split(data);

        queue<TreeNode *> q;

        TreeNode *root = new TreeNode(stoi(str_list[0]));

        q.push(root);

        int iter = 1;

        while (iter == 0 || !q.empty()) {

            TreeNode *node = q.front(); q.pop();

            string val = str_list[iter];

            if (val != "#") {

                node -> left = new TreeNode(stoi(val));

                q.push(node -> left);

            }

            iter++;

            if (iter == str_list.size()) {

                return root;

            }

            val = str_list[iter];

            if (val != "#") {

                node -> right = new TreeNode(stoi(val));

                q.push(node -> right);

            }

            iter++;

            if (iter == str_list.size()) {

                return root;

            }

        }

        return root;

    }

};

// Your Codec object will be instantiated and called as such:

// Codec ser, deser;

// TreeNode* ans = deser.deserialize(ser.serialize(root));

Insert interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

============

in-place one:

vector<Interval> adjustEnd(vector<Interval>& intervals, int i, Interval newInterval) {

        int j = i + 1;

        while (j <= intervals.size()) {

            if (j == intervals.size()) {

                intervals[i].end = max(newInterval.end, intervals[i].end);

                return intervals;

            }

            if (newInterval.end < intervals[j].start) {

                intervals[i].end = max(newInterval.end, intervals[i].end);

                return intervals;

            } else if (newInterval.end >= intervals[j].start &&

                        newInterval.end <= intervals[j].end) {

                intervals[i].end = intervals[j].end;

                intervals.erase(intervals.begin() + j);

                return intervals;

            } else {

                intervals.erase(intervals.begin() + j);

            }

        }

        return intervals;

    }

    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {

        if (intervals.size() == 0) {

            intervals.push_back(newInterval);

            return intervals;

        }

        int size = intervals.size();

        if (newInterval.start > intervals[size - 1].end) {

            intervals.push_back(newInterval);

            return intervals;

        }

        int i = 0;

        while (i < intervals.size()) {

            if (newInterval.start >= intervals[i].start &&

                newInterval.start <= intervals[i].end) {

                return adjustEnd(intervals, i, newInterval);

            } else if (newInterval.start < intervals[i].start) {

                if (newInterval.end < intervals[i].start) {

                    intervals.insert(intervals.begin() + i, newInterval);

                    return intervals;

                } else if (newInterval.end >= intervals[i].start) {

                    intervals[i].start = newInterval.start;

                    return adjustEnd(intervals, i, newInterval);

                }

            }

            i++;

        }

        

        return intervals;

    }


=============
Short and elegant below in java:

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    if(newInterval == null) return intervals;
    int first = 0;
    /*find first overlapping interval*/
    while(first < intervals.size() && newInterval.start > intervals.get(first).end)
        first++;   
    /*merge intervals */
    while(first < intervals.size() && newInterval.end >= intervals.get(first).start)
    {
        newInterval = new Interval(Math.min(newInterval.start,intervals.get(first).start),
                                  Math.max(newInterval.end,intervals.get(first).end));
        intervals.remove(first);
    }
    intervals.add(first,newInterval);
    return intervals;
}

===============  Recent one ========

class Solution {
public:
    bool overlap(vector<int> interval, int& first, int& second) {
        if ((first >= interval[0] && first <= interval[1]) ||
            (second >= interval[0] && second <= interval[1])) {
            
            first = min(interval[0], first);
            second = max(interval[1], second);
            return true;
        }
        return false;
    }

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> sol;
        int first = newInterval[0];
        int second = newInterval[1];
        
        if (intervals.size() == 0) {
            sol.push_back(vector<int> {first, second});
            return sol;
        }
        
        int i = 0;
        bool merged = false;
        
        for (i = 0; i < intervals.size(); i++) {
            bool is_overlap = overlap(intervals[i], first, second);
            if (!is_overlap) {
                if (second < intervals[i][0]) {
                    if (!merged) {
                        sol.push_back(vector<int> {first, second});
                        merged = true;
                    }
                    sol.push_back(intervals[i]);
                } else if (intervals[i][1] < first) {
                    sol.push_back(intervals[i]);
                }
            }
        }
        
        if (!merged) {
            sol.push_back(vector<int> {first, second});
        }
        return sol;
    }

};


=========== Another one =======
class Solution {
public:
    
    int overlap(vector<int>& newInterval, vector<int>& interval) {
        if (newInterval[1] < interval[0]) {
            // newInterval < interval
            return -1;
        } else if (newInterval[0] > interval[1]) {
            // newInterval > interval
            return 1;
        } else {
            // Merge.
            return 0;
        }
    }
    
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> sol;
        if (intervals.size() == 0) {
            sol.push_back(newInterval);
            return sol;
        }
        
        int iter = 0;
        while (iter < intervals.size()) {
            int option = overlap(newInterval, intervals[iter]);
            if (option == 0) {
                // Merge going-on
                newInterval[0] = min(newInterval[0], intervals[iter][0]);
                newInterval[1] = max(newInterval[1], intervals[iter][1]);
            } else if (option == -1) {
                // merge completed.
                sol.push_back(newInterval);
                while (iter < intervals.size()) {
                    sol.push_back(intervals[iter]);
                    iter++;
                }
                return sol;
            } else {
                // Merge ahead
                sol.push_back(intervals[iter]);
            }
            iter++;
        }
        sol.push_back(newInterval);
        return sol;
    }

};