Serialize And Deserialize Binary Tree

                                            
/**
 * 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 == NULL) {
            return "null";
        }
        
        return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        return deserializeHelper(ss);
    }
    
private:
    TreeNode* deserializeHelper(stringstream& ss) {
        string str;
        getline(ss, str, ',');
        
        if(str == "null") {
            return NULL;
        } else {
            TreeNode* root = new TreeNode(stoi(str));
            root->left = deserializeHelper(ss);
            root->right = deserializeHelper(ss);
            return root;
        }
    }
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Codec {
    function serialize($root) {
        if ($root === null) {
            return "null,";
        }
        
        $leftSerialized = $this->serialize($root->left);
        $rightSerialized = $this->serialize($root->right);
        
        return $root->val . "," . $leftSerialized . $rightSerialized;
    }
    
    function deserialize($data) {
        $queue = explode(",", $data);
        return $this->buildTree($queue);
    }
    
    function buildTree(&$queue) {
        $val = array_shift($queue);
        
        if ($val === "null") {
            return null;
        }
        
        $node = new TreeNode($val);
        $node->left = $this->buildTree($queue);
        $node->right = $this->buildTree($queue);
        
        return $node;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Codec() {
    // Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        if (root == null) {
            return "null"
        }
        
        val leftSerialized = serialize(root.left)
        val rightSerialized = serialize(root.right)
        
        return "${root.`val`},$leftSerialized,$rightSerialized"
    }
    
    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        val dataList = data.split(",")
        val queue: Queue<String> = LinkedList(dataList)
        return deserializeHelper(queue)
    }
    
    private fun deserializeHelper(queue: Queue<String>): TreeNode? {
        val value = queue.poll()
        if (value == "null") {
            return null
        }
        
        val node = TreeNode(value.toInt())
        node.left = deserializeHelper(queue)
        node.right = deserializeHelper(queue)
        
        return node
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var _value: Int) {
 *   var value: Int = _value
 *   var left: TreeNode = null
 *   var right: TreeNode = null
 * }
 */
class Codec {
    // Encodes a list of strings to a single string.
    def serialize(root: TreeNode): String = {
        if (root == null) return "null"
        
        val leftSerialized = serialize(root.left)
        val rightSerialized = serialize(root.right)
        
        root.value.toString + "," + leftSerialized + "," + rightSerialized
    }
    
    // Decodes a single string to a list of strings.
    def deserialize(data: String): TreeNode = {
        var queue = scala.collection.mutable.Queue[String](data.split(","):_*)
        
        def helperDeserialize(): TreeNode = {
            val value = queue.dequeue()
            if (value == "null") return null
            
            val node = new TreeNode(value.toInt)
            node.left = helperDeserialize()
            node.right = helperDeserialize()
            
            node
        }
        
        helperDeserialize()
    }
}

To solve this coding challenge of serializing and deserializing a binary tree, we need to convert the tree into a single string representation and subsequently reconstruct the tree from that string. This is critical in scenarios like storing tree data in files or transmitting it over a network where we need a consistent format.

Explanation

Serialization involves converting the structure into a flat representation (usually a string), while deserialization is the process of reconstructing the tree structure from this flat representation. The key steps involve:

Serialize : This process should convert the tree into a string format. A pre-order traversal (root, left, right) is a common approach, providing a straightforward way to serialize the tree. During this traversal, we record the value of the nodes as well as markers (e.g., "null") to denote the absence of child nodes.
Deserialize : This reverse process takes the string created during serialization and reconstructs the tree. By reading the string tokens sequentially, we can reconstruct the tree structure as we parse the node values and their hierarchical relationships.

Let's cover the steps in detail for both serialization and deserialization.

Step-by-Step Explanation

Serialization

Base Case : When the current node is
null

, return "null" to denote the absence of a node.
Recursive Case : Convert the current node's value to a string. Then, recursively serialize the left child and the right child. Combine these parts using a delimiter, such as a comma, to form the full serialized string for the current subtree.

Deserialization

Input Parsing : Split the serialized string by the delimiter (comma) to process each component one at a time.
Reconstruction : Read each token sequentially. If a token is "null", it indicates the absence of a node, so return
null

. Otherwise, convert the token to an integer to construct a new TreeNode. Recursively reconstruct the left and right children for each node.

Detailed Steps in Pseudocode

Serialization Pseudocode

                                            
// Function to serialize a tree to a single string
function serialize(root):
    // Base case: If the node is null, return "null"
    if root is null:
        return "null"
    
    // Get the value of the current node
    rootValue = to_string(root.val)
    
    // Serialize the left subtree
    leftSerialized = serialize(root.left)
    
    // Serialize the right subtree
    rightSerialized = serialize(root.right)
    
    // Combine the results with commas separating them
    return rootValue + "," + leftSerialized + "," + rightSerialized

Deserialization Pseudocode

                                            
// Function to deserialize a string to a tree
function deserialize(data):
    // Split the input string by commas
    dataList = split(data, ",")
    
    // Helper function to recursively deserialize the tree
    function deserializeHelper(dataList):
        // Get the next value from the list
        value = dataList.pop(0)
        
        // Base case: If the value is "null", return null
        if value == "null":
            return null
        
        // Convert the value to an integer to create a new node
        root = new TreeNode(to_integer(value))
        
        // Recursively construct the left subtree
        root.left = deserializeHelper(dataList)
        
        // Recursively construct the right subtree
        root.right = deserializeHelper(dataList)
        
        return root
    
    // Call the helper function with the data list
    return deserializeHelper(dataList)

This pseudocode lays down a clear path for serializing and deserializing binary trees. The traversal approach ensures that we capture the complete structure of the binary tree, while the use of a comma as a delimiter helps us parse the string efficiently during deserialization. By leveraging recursion, we can handle trees of varying sizes and depths consistently.