coderz.py

Problem Statement (Asked By Google)

Given the root of a binary tree, create two functions:

1. serialize(root) – Converts the binary tree into a string representation.
2. deserialize(s) – Reconstructs the binary tree from its string representation.

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

Problem link: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

---

Solution:

There are multiple ways to serialize and deserialize a binary tree, so your solution may look different, and that’s completely fine. Here, we’ll explore one specific approach.

We begin by deciding how we want the serialized tree to appear. A good serialized format should contain just enough information to reconstruct the entire tree. One possible format, inspired by S-expressions in Lisp, could represent a tree-like Node(1, Node(2), Node(3)) as (1 (2 () ()) (3 () ())), where the empty parentheses signify null nodes.

We can simplify this format to reduce data size for transmission or storage further. Instead of using (), we can replace null nodes with # and eliminate unnecessary parentheses. For instance, a tree serialized as 1 2 # # 3 # # provides the same information. From this format, leaf nodes can be identified as those having the structure value # #, and we can infer the tree structure accordingly.

// TreeNode class definition
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class TreeSerialization {
    
    // Serialize the tree
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        return root.val + " " + serialize(root.left) + " " + serialize(root.right);
    }
    
    // Deserialize the tree
    public static TreeNode deserialize(String data) {
        String[] values = data.split(" ");
        return helper(new java.util.Iterator<String>() {
            private int index = 0;
            public boolean hasNext() {
                return index < values.length;
            }
            public String next() {
                return values[index++];
            }
        });
    }

    private static TreeNode helper(java.util.Iterator<String> vals) {
        String val = vals.next();
        if (val.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = helper(vals);
        node.right = helper(vals);
        return node;
    }

    // Main method for testing
    public static void main(String[] args) {
        // Creating a sample tree: Node(1, Node(2), Node(3))
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        
        // Serialization
        String serialized = serialize(root);
        System.out.println("Serialized: " + serialized);
        
        // Deserialization
        TreeNode deserialized = deserialize(serialized);
        System.out.println("Deserialized Root Value: " + deserialized.val);
    }
}

Explanation:

1. Serialization:
   • The tree is traversed using a preorder traversal (root → left → right).
   • Each node’s value is added to the serialized string.
   • Null nodes are represented by #.
2. Deserialization:
   • The serialized string is split into an array of values.
   • We use an iterator to process each value one by one.
   • If a value is #, it signifies a null node.
   • Otherwise, create a new TreeNode with the value, and recursively build its left and right subtrees.

Time Complexity: O(N) — The entire tree is traversed once for serialization and once for deserialization.
Space Complexity: O(N) — The serialized string and recursion stack (or iterator) consume memory.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.