# LeetCode #449 Serialize and Deserialize BST

• ## Solution

We can use different forms to serialize the tree and the deserialize method depend on how we serialize it.

### Part #1 Serialize

Since the left child and right child are different, so we have store both the children even if one of them is null. We can consider the form like this:

``````    { val { left.val {...} {...} } { right.val {...} {...} } }
``````

Thus, we can traverse the tree in pre-order to construct the result. The length of result is 4n + Σlength(val) .

#### java

`````` // Encodes a tree to a single string.
public String serialize(TreeNode root) {
return serial(root).toString();
}
private StringBuilder serial(TreeNode root){ // traverse the tree in pre-order
if(root == null) return new StringBuilder("{}");
return new StringBuilder("{")
.append(root.val)    //val
.append(serialize(root.left))  //left
.append(serialize(root.right))  //right
.append("}");
}
``````

### Complexity Analysis

• Time complexity : O(n). Traverse the tree in pre-order.

### Part #2 Deserialize

In the same way, we can deserialize the string in pre-order

#### java

`````` // Decodes your encoded data to tree.
int begin = 0;
public TreeNode deserialize(String data) {
return findChild(data);
}
private int findVal(String data){
int index = begin;
while(data.charAt(index)!='{'){index++;}
int val = Integer.parseInt(data.substring(begin, index));
begin = index;
return val;
}
private TreeNode findChild(String data){
if(data.charAt(begin+1) == '}') {
begin += 2;
return null;
}
begin++;
TreeNode root = new TreeNode(findVal(data));
root.left = findChild(data);
root.right = findChild(data);
begin++;
return root;
}
``````

### Complexity Analysis

• Time complexity : O(n). We just traverse the string once.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.