Welcome to Subscribe On Youtube

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-Serialize-and-Deserialize-Binary-Tree 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));

############

/**
 * 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) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.substring(0, sb.length() - 1);
    }

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || "".equals(data)) {
            return null;
        }
        String[] s = data.split(",");
        return build(s, 0, s.length - 1);
    }

    private TreeNode build(String[] s, int l, int r) {
        if (l > r) {
            return null;
        }
        int idx = r + 1;
        TreeNode root = new TreeNode(Integer.valueOf(s[l]));
        for (int i = l + 1; i <= r; ++i) {
            if (Integer.valueOf(s[i]) > root.val) {
                idx = i;
                break;
            }
        }
        root.left = build(s, l + 1, idx - 1);
        root.right = build(s, idx, r);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

  • class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
         ostringstream os;
         serialize(root, os);
         return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream is(data);
        return deserialize(is);
    }
    
    void serialize(TreeNode* root, ostringstream& os) {
        if (!root) os << "# ";
        else {
            os << root->val << " ";
            serialize(root->left, os);
            serialize(root->right, os);
        }
    }
    
    TreeNode* deserialize(istringstream& is) {
        string val = "";
        is >> val;
        if (val == "#") return NULL;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserialize(is);
        node->right = deserialize(is);
        return node;
    }
};

  • class Codec:
    # Encodes a tree to a single string.
    def serialize(self, root: TreeNode) -> str:
        sb = []
        self.serializeHelper(root, sb)
        return ','.join(sb)

    def serializeHelper(self, root: TreeNode, sb: List[str]):
        if not root:
            return
        sb.append(str(root.val))
        self.serializeHelper(root.left, sb)
        self.serializeHelper(root.right, sb)

    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> TreeNode:
        if not data:
            return None
        q = deque(data.split(','))
        return self.deserializeHelper(q, float('-inf'), float('inf'))

    def deserializeHelper(self, q: deque, lower: int, upper: int) -> TreeNode:
        if not q:
            return None
        s = q[0]
        val = int(s)

        # here is the key, not in sub-tree range then meaning stop
        if val < lower or val > upper:
            return None
        q.popleft()
        root = TreeNode(val)
        root.left = self.deserializeHelper(q, lower, val)
        root.right = self.deserializeHelper(q, val, upper)
        return root

#################

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Codec:
    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string."""

        def dfs(root):
            if root is None:
                return
            nonlocal t
            t.append(str(root.val))
            t.append(',')
            dfs(root.left)
            dfs(root.right)

        if root is None:
            return ''
        t = []
        dfs(root)
        return ''.join(t[:-1])

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree."""

        def build(s, l, r):
            if l > r:
                return None
            root = TreeNode(int(s[l]))
            idx = r + 1
            for i in range(l + 1, r + 1):
                if int(s[i]) > root.val:
                    idx = i
                    break
            root.left = build(s, l + 1, idx - 1)
            root.right = build(s, idx, r)
            return root

        if not data:
            return None
        s = data.split(',')
        return build(s, 0, len(s) - 1)


# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
  def serialize(self, root):
    """Encodes a tree to a single string.
    
    :type root: TreeNode
    :rtype: str
    """
    stack = [(1, root)]
    ans = []
    while stack:
      pc, node = stack.pop()
      if not node:
        continue
      if pc == 0:
        ans.append(str(node.val))
      else:
        stack.append((1, node.right))
        stack.append((1, node.left))
        stack.append((0, node))
    return ",".join(ans)

  def deserialize(self, data):
    """Decodes your encoded data to tree.
    
    :type data: str
    :rtype: TreeNode
    """
    if not data:
      return None
    vals = data.split(",")
    preOrder = map(int, vals)
    inOrder = sorted(preOrder)
    self.preIdx = 0
    d = {}
    for i in range(0, len(inOrder)):
      d[inOrder[i]] = i

    def helper(preOrder, start, end, inOrder, d):
      if start <= end:
        rootVal = preOrder[self.preIdx]
        self.preIdx += 1
        root = TreeNode(rootVal)
        midPos = d[rootVal]
        root.left = helper(preOrder, start, midPos - 1, inOrder, d)
        root.right = helper(preOrder, midPos + 1, end, inOrder, d)
        return root

    return helper(preOrder, 0, len(inOrder) - 1, inOrder, d)

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


  • /**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return ""
	}
	data := &strings.Builder{}
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		data.WriteString(strconv.Itoa(root.Val))
		data.WriteByte(' ')
		dfs(root.Left)
		dfs(root.Right)
	}
	dfs(root)
	return data.String()[0 : data.Len()-1]
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}
	vals := strings.Split(data, " ")
	i := 0
	var dfs func(int, int) *TreeNode
	dfs = func(mi, mx int) *TreeNode {
		if i == len(vals) {
			return nil
		}
		x, _ := strconv.Atoi(vals[i])
		if x < mi || x > mx {
			return nil
		}
		i++
		root := &TreeNode{Val: x}
		root.Left = dfs(mi, x)
		root.Right = dfs(x, mx)
		return root
	}
	return dfs(math.MinInt64, math.MaxInt64)
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor()
 * deser := Constructor()
 * tree := ser.serialize(root)
 * ans := deser.deserialize(tree)
 * return ans
 */

All Problems

All Solutions