Java Solution with Explanation using an Example for better understanding | Queue | Preorder
EXPLANATION\n\nTaking Example 1 of the question: BST = [2, 1, 3]\n\n1. SERIALIZE / ENCODE: Use Preorder Traversal to serialize the BST where each node value is 
**EXPLANATION**\n\nTaking Example 1 of the question: ***BST = [2, 1, 3]***\n\n1. **SERIALIZE / ENCODE**: Use **Preorder Traversal** to serialize the BST where each node value is separated by a comma (**","**).  So after serialization of the above tree, we will return a string like this: **2,1,3**.\n\n2. **DESERIALIZE / DECODE**: Here comes the importance of using **Preorder Traversal** in the above step.  By doing this, we ensured that all the parent nodes (roots) come before the children nodes *(all **left** nodes followed by all **right** nodes)*.  So all we have to do now is **Add** all the nodes in the string into a **Queue** and keep creating the tree node-by-node.  For this, the steps are:\n\ni) Repeat the below steps until **queue** is not empty.\nii) Pop out a node from the front of the queue.  If the node is not null, then create a new node by using it\'s value.\niii) Recursively call the *Deserialize Function* to store all the **left children** first and then again to store all the **right children** of a particular node.\niv) Return the node.\n\n*For example, our serialized string was **2,1,3***.  So we add them in the queue one-by-one.  So our **queue** looks like **[2,1,3]**.\n\nNow, popping **2** from the queue, we are left with **[1,3]**.\n\nRecursively call the function to store its left child.  New node is **1**, and both its **left child** and **right child** will be stored as null in the next two recursive calls.  So **1** gets stored as the **Left Child** of node **2**.  Similarly, **3** gets stored as the **Right Child** of node **2**.\n\nIn the end, we return node **2** which is the root of the deserialized tree. That\'s it and you have your deserialized tree.\n\n*------Please **upvote** if you liked the solution.  Please put your doubts/queries in the comments section below.  I will try my best to answer them.------*\n```\npublic class Codec {\n\n    // Encodes a tree to a single string.\n    public String serialize (TreeNode root) {\n        if (root == null)\n            return "";\n        return String.valueOf (root.val) + "," + serialize (root.left) + "," + serialize (root.right);\n        \n    }\n\n    // Decodes your encoded data to tree.\n    public TreeNode deserialize (String data) {\n        String S [] = data.split (",");\n        Queue <String> queue = new LinkedList ();\n        for (String s: S)\n            queue.add (s);\n        return deserializeUtil (queue);\n    }\n    \n    public TreeNode deserializeUtil (Queue <String> queue) {\n        while (!queue.isEmpty ()) {\n            String s = queue.poll ();\n            if (s.equals (""))\n                return null;\n            TreeNode node = new TreeNode (Integer.valueOf (s));\n            node.left = deserializeUtil (queue);\n            node.right = deserializeUtil (queue);\n            return node;\n        }\n        return null;\n    }\n}\n```
[]