Formatted question description: https://leetcode.ca/all/449.html

449. Serialize and Deserialize BST

Level

Medium

Description

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution

For a binary search tree, its inorder traversal must be sorted in ascending order. Therefore, obtaining its preorder traversal is sufficient to reconstruct the binary search tree.

In serialize, obtain the binary search tree’s inorder traversal where the solution to problem 144 can be used, convert it into a string, and return.

In deserialize, split te values from the string data to obtain the preorder traversal. Obtain its inorder traversal by sorting the elements. Then reconstruct the binary search tree using the preorder traversal and the inorder traversal where the solution to problem 105 and the solution to problem 1008 can be used, and return.

Difference with #297 - Serialize and Deserialize Binary Tree

The difference is the bold The encoded string should be as compact as possible here. The special property of binary search trees compared to general binary trees allows a more compact encoding. So while the solutions to problem #297 still work here as well, they’re not as good as they should be.

  • For Binary tree solution, we need to have “#” or “null” to indicate null node in the serialized string.
  • However, for BST, we don’t need such “#” which make it more compact.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.toString();
        }

        public void serialize(TreeNode root, StringBuilder sb) {
            if (root == null) return;
            sb.append(root.val).append(",");
            serialize(root.left, sb);
            serialize(root.right, sb);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.isEmpty()) return null;
            Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
            return deserialize(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        public TreeNode deserialize(Queue<String> q, int lower, int upper) {
            if (q.isEmpty()) return null;
            String s = q.peek();
            int val = Integer.parseInt(s);
            if (val < lower || val > upper) return null;

            q.poll();
            TreeNode root = new TreeNode(val);
            root.left = deserialize(q, lower, val);
            root.right = deserialize(q, val, upper);

            return root;
        }
    }

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

All Problems

All Solutions