Serialize and Deserialize Binary Tree hard

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 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.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and efficient.

Example 1

Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]

Example 2

Input: root = [] Output: []

Steps

The serialization process will use a preorder traversal (root, left, right). We'll use a special marker, like "N", to represent null nodes. The deserialization process will read this string and reconstruct the tree using a similar preorder approach.

1. Serialization:

   • Perform a preorder traversal of the binary tree.
   • For each node, append its value to the string.
   • If a node is null, append the "N" marker.
   • Separate node values with commas.

2. Deserialization:

   • Split the serialized string by commas.
   • Use a queue to keep track of nodes that need children added.
   • Read values from the string.
   • If the value is not "N", create a new node and add it to the tree.
   • If the value is "N", indicate a null child.
   • Move through the queue, adding left and right children.

Explanation

Serialization: The preorder traversal ensures that we always process the root before its children. This is crucial for reconstruction. The "N" marker allows us to distinguish between null nodes and nodes with actual values.

Deserialization: The queue helps manage the tree construction. We start with the root. Then, for each node, we add its left child and then its right child (as per preorder). The queue is essential to keep track of the current node we're populating.

Code

import java.util.*;

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "N";
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("N,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("N")) return null;
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("N")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

Complexity

Serialization:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(N) in the worst case (a skewed tree), due to the recursive calls. In average case, it's O(log N) for balanced trees.

Deserialization:

• Time Complexity: O(N). We process each node value once.
• Space Complexity: O(N) in the worst case (skewed tree) due to the queue and recursion depth. In average case, it's O(log N) for balanced trees.