Serialization and De-serialization of an BST

https://leetcode.com/problems/serialize-and-deserialize-bst/, I've solved a similar problem before for a generic tree, but couldn't quite remember the solution. This one here uses a DFS-recursion to serialize and use a non-recursive method using a stack for de-serialization. Here is the problem statement:

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Let's take a look at the serialization: we'll be going down the tree in an DFS and will be encoding the tree in the following format (context-free grammar):
EncodedTree = ""
EncodedTree = <node value> + EncodedTreeNotEmpty
EncodedTreeNotEmpty = <node value> + L + EncodedTreeNotEmpty
EncodedTreeNotEmpty = <node value> + R + EncodedTreeNotEmpty
EncodedTreeNotEmpty = *
Here is an example of a serialized tree:
"10L5L1*R8**R15L11*R20R100R142*****"
The de-serialization will use a stack to control the state of the nodes, but the logic will be the following:
  • Handle the base case
  • Whenever you see an "L", peek the stack, create the left node, push it back into the stack
  • Whenever you see an "R", peek the stack, create the right node, push it back into the stack
  • Whenever you see an "*", pop out of the stack
The key point is to "peek: the item in the stack in steps 2 and 3 rather than pop. You do that until you reach the end of the string. And that's it! Cheers, Marcelo.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace LeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode tree = new TreeNode(10);
            tree.left = new TreeNode(5);
            tree.right = new TreeNode(15);
            tree.left.left = new TreeNode(1);
            tree.left.right = new TreeNode(8);
            tree.right.left = new TreeNode(11);
            tree.right.right = new TreeNode(20);
            tree.right.right.right = new TreeNode(100);
            tree.right.right.right.right = new TreeNode(142);
            Codec codec = new Codec();
            string codedTree = codec.serialize(tree);
            Console.WriteLine(codedTree);

            TreeNode dTree = codec.deserialize(codedTree);
            PrintTree(dTree);
        }

        static void PrintTree(TreeNode tree)
        {
            if (tree == null) return;
            Console.WriteLine(tree.val);
            PrintTree(tree.left);
            PrintTree(tree.right);
        }
    }
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    public class Codec
    {

        // Encodes a tree to a single string.
        public string serialize(TreeNode root)
        {
            if (root == null) return "";
            string retVal = root.val.ToString();
            if (root.left != null) retVal += "L" + serialize(root.left);
            if(root.right != null) retVal += "R" + serialize(root.right);
            return retVal + "*";
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(string data)
        {
            if (String.IsNullOrEmpty(data)) return null;

            Stack stack = new Stack();
            int index = 0;
            int val = GetTreeValue(data, ref index);

            TreeNode tree = new TreeNode(val);
            TreeNode retVal = tree;
            stack.Push(tree);
            while (index < data.Length)
            {
                if (index < data.Length && data[index] == 'L')
                {
                    TreeNode treeFromStack = (TreeNode)stack.Peek();
                    index++;
                    val = GetTreeValue(data, ref index);
                    treeFromStack.left = new TreeNode(val);
                    stack.Push(treeFromStack.left);
                }
                else if (index < data.Length && data[index] == 'R')
                {
                    TreeNode treeFromStack = (TreeNode)stack.Peek();
                    index++;
                    val = GetTreeValue(data, ref index);
                    treeFromStack.right = new TreeNode(val);
                    stack.Push(treeFromStack.right);
                }
                else
                {
                    if(stack.Count > 0) stack.Pop();
                    index++;
                }
            }

            return retVal;
        }

        private int GetTreeValue(string data, ref int index)
        {
            int val = 0;
            while (index < data.Length && data[index] >= '0' && data[index] <= '9')
            {
                val = 10 * val + (int)(data[index] - '0');
                index++;
            }
            return val;
        }
    }
}

Comments

  1. I love these recurrence problems! I decided to maximize ease of serialization/deserialization, so I'm storing sentinels to identify nulls, which are potentially result in some extra used space, but it's super easy to code and understand:

    /**
    * 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) {
    if (root == nullptr) return "N";
    return to_string(root->val) + "|" + serialize(root->left) + "|" + serialize(root->right);
    }

    TreeNode* deserialize(istringstream& data) {
    if (data.eof()) return nullptr;
    if (data.peek() == 'N') {
    char sentinel; data >> sentinel;
    return nullptr;
    }
    int val; data >> val;
    TreeNode* node = new TreeNode(val);
    char divider; data >> divider;
    node->left = deserialize(data);
    data >> divider;
    node->right = deserialize(data);
    return node;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(const string& data) {
    istringstream data_stream(data);
    return deserialize(data_stream);
    }
    };

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

    Thanks for sharing this awesome problem!

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

Prompt Engineering and LeetCode

ProjectEuler Problem 719 (some hints, but no spoilers)