Serialize and Deserialize Binary Tree - LeetCode 297 Solution in python

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.

You may serialize the following tree:

as [1,2,3,null,null,4,5]

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:

Serialization: We'll use a preorder traversal (root, left, right). If a node is null, we'll represent it with the string "null". We'll separate node values with commas.
Deserialization: We'll use the serialized string to reconstruct the tree. We'll use a queue to keep track of nodes to process and read values from the string using a queue-like approach.

Explanation:

Serialization: The preorder traversal ensures we reconstruct the tree in the correct order. We start at the root, then process its left subtree, and finally its right subtree. By representing null nodes explicitly, we can accurately reconstruct the tree's structure.

Deserialization: We create a queue from our serialized string, then start building the tree. We pop a value from the queue, and if it's not "null", we create a new node. Then, we recursively build the left and right subtrees by calling the deserialization function again, pulling values from the queue to create the children.

Code:

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function serialize(root: TreeNode | null): string {
    if (root === null) return "null";
    return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data: string): TreeNode | null {
    const nodes = data.split(",");
    let i = 0;
    const buildTree = (): TreeNode | null => {
        if (i >= nodes.length || nodes[i] === "null") {
            i++;
            return null;
        }
        const node = new TreeNode(parseInt(nodes[i++]));
        node.left = buildTree();
        node.right = buildTree();
        return node;
    };
    return buildTree();
}

// Example usage:
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
const serialized = serialize(root);
console.log("Serialized:", serialized); // Output: Serialized: 1,2,4,null,null,5,null,null,3,null,null

const deserialized = deserialize(serialized);
console.log("Deserialized:", deserialized); // Output: Deserialized: TreeNode { val: 1, left: TreeNode, right: TreeNode } (Structure will vary, but should be the same tree)


//Test with empty tree
const emptyRoot: TreeNode | null = null;
const serializedEmpty = serialize(emptyRoot);
console.log("Serialized empty:", serializedEmpty); // Output: Serialized empty: null

const deserializedEmpty = deserialize(serializedEmpty);
console.log("Deserialized empty:", deserializedEmpty); // Output: Deserialized empty: null

Complexity:

Time Complexity: Both serialization and deserialization are O(N), where N is the number of nodes in the tree. We visit each node once.
Space Complexity: The space complexity is O(N) for both functions as well, primarily due to the recursive call stack during traversal and the string used for serialization. In the worst case (a skewed tree), the recursive call stack could reach a depth of N.