449. Serialize and Deserialize BST

Description

Serialization is 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 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.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
0 <= Node.val <= 10⁴
The input tree is guaranteed to be a binary search tree.

Solutions

The serialization and deserialization processes leverage the BST property that left child nodes have smaller values and right child nodes have larger values than their parent node. Here’s a detailed explanation of how each part works:

Serialization

Method: serialize

Starts the serialization process by calling a helper method serializeHelper with the root of the tree and an empty list sb.
The helper method performs a preorder traversal (root, left, right) of the tree. For each node, it appends the node’s value to sb. If a node is None, the traversal simply returns without appending anything, effectively skipping null nodes.
After the traversal, sb contains all the node values in preorder. The method returns a string by joining all elements in sb with commas.

Method: serializeHelper

A recursive function that appends the value of the current node to the list sb, then recursively calls itself for the left and right children of the current node. This results in a preorder traversal of the tree.

Deserialization

Method: deserialize

Begins by splitting the input string data on commas, converting it into a deque q for efficient popping from the front. The deque represents the preorder traversal of the tree.
Calls a helper method deserializeHelper, passing q and initial lower and upper bounds. These bounds are used to ensure the values fit within the expected range for a BST. Initially, the bounds are set to negative and positive infinity, allowing any value.

Method: deserializeHelper

A recursive function that builds the BST based on the preorder values in q. It checks if the current value (the front of q) falls within the expected lower and upper bounds. If it doesn’t, the method returns None, indicating that the current value does not belong to the subtree being processed.
If the value is within bounds, it is popped from q and used to create a new TreeNode. The method then recursively calls itself to construct the left and right subtrees, adjusting the lower and upper bounds accordingly. For the left child, the upper bound becomes the parent node’s value, and for the right child, the lower bound becomes the parent node’s value.
This process ensures that each value is placed correctly according to BST rules, rebuilding the tree from its preorder representation.

Example

Consider the BST:

    2
   / \
  1   3

Serialization: The serialize method would produce the string "2,1,3".

Deserialization: Given the string "2,1,3", the deserialize method rebuilds the original BST by ensuring that 1 is placed as the left child of 2 and 3 as the right child, based on their values.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private int i;
    private List<String> nums;
    private final int inf = 1 << 30;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        nums = new ArrayList<>();
        dfs(root);
        return String.join(" ", nums);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || "".equals(data)) {
            return null;
        }
        i = 0;
        nums = Arrays.asList(data.split(" "));
        return dfs(-inf, inf);
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        nums.add(String.valueOf(root.val));
        dfs(root.left);
        dfs(root.right);
    }

    private TreeNode dfs(int mi, int mx) {
        if (i == nums.size()) {
            return null;
        }
        int x = Integer.parseInt(nums.get(i));
        if (x < mi || x > mx) {
            return null;
        }
        TreeNode root = new TreeNode(x);
        ++i;
        root.left = dfs(mi, x);
        root.right = dfs(x, mx);
        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;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) {
            return "";
        }
        string data = "";
        function<void(TreeNode*)> dfs = [&](TreeNode* root) {
            if (!root) {
                return;
            }
            data += to_string(root->val) + " ";
            dfs(root->left);
            dfs(root->right);
        };
        dfs(root);
        data.pop_back();
        return data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) {
            return nullptr;
        }
        vector<int> nums = split(data, ' ');
        int i = 0;
        function<TreeNode*(int, int)> dfs = [&](int mi, int mx) -> TreeNode* {
            if (i == nums.size() || nums[i] < mi || nums[i] > mx) {
                return nullptr;
            }
            int x = nums[i++];
            TreeNode* root = new TreeNode(x);
            root->left = dfs(mi, x);
            root->right = dfs(x, mx);
            return root;
        };
        return dfs(INT_MIN, INT_MAX);
    }

    vector<int> split(const string& s, char delim) {
        vector<int> tokens;
        stringstream ss(s);
        string token;
        while (getline(ss, token, delim)) {
            tokens.push_back(stoi(token));
        }
        return tokens;
    }
};

// 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;

# 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

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 # leave i-node to other tree branches
        q.popleft()
        root = TreeNode(val)
        root.left = self.deserializeHelper(q, lower, val)
        root.right = self.deserializeHelper(q, val, upper)
        return root


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

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

        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            nums.append(root.val)
            dfs(root.left)
            dfs(root.right)

        nums = []
        dfs(root)
        return " ".join(map(str, nums))

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

        def dfs(mi: int, mx: int) -> Optional[TreeNode]:
            nonlocal i
            if i == len(nums) or not mi <= nums[i] <= mx:
                return None # leave i-node to other tree branches
            x = nums[i]
            root = TreeNode(x)
            i += 1
            root.left = dfs(mi, x)
            root.right = dfs(x, mx)
            return root

        nums = list(map(int, data.split()))
        i = 0
        return dfs(-inf, inf)


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

# 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
 */

449 - Serialize and Deserialize BST

449. Serialize and Deserialize BST

Description

Solutions

Serialization

Deserialization

Example

All Problems

All Solutions

Welcome to Subscribe On Youtube

449. Serialize and Deserialize BST

Description

Solutions

Serialization

Deserialization

Example

All Problems

All Solutions