LC 449. Serialize and Deserialize BST

Problem

Solution in Python

Most tree problems can be solved recursively. This one is the same. A preorder traversal is used here to serialize and deserialize the BST tree. Preorder is the order of “root, left, right”. Since it is a BST, we know that given a list of node values, the first element is the root. For the rest part,

left = [val < root_val for val in rest]

right = [val >root_val for val in rest]

Then we can solve the problem recursively, which is :

suppose we have node_vals, we will have

root_val = node_vals[0]

rest = node_vals[1:]

root_node = TreeNode(root_val)

left_node = [val < root_val for val in rest]

right_node = [val >root_val for val in rest]

root.left, root.right = left_node, right_node

Done.

# 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 helper(node):
if node is None:return []
return [node.val] + helper(node.left) + helper(node.right)
node_vals = helper(root)
return ",".join(str(val) for val in node_vals)
def deserialize(self, data: str) -> TreeNode:
"""Decodes your encoded data to tree.
"""
if not data:return None
node_vals = data.split(',')
node_vals = [int(val) for val in node_vals]
def helper(node_vals):
if not node_vals:return None
root = TreeNode(node_vals[0])
left_node = helper([val for val in node_vals[1:] if val < node_vals[0]])
right_node = helper([val for val in node_vals[1:] if val > node_vals[0]])
root.left = left_node
root.right = right_node
return root
return helper(node_vals)
# 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

For more binary tree problems see my previous post.

Thanks for reading. Happy coding.

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

KOTLIN —Mobile cross platform

CSS — The Styling Language.

Automated slack deployment notification from Jenkins

Windows 11 — A full and honest Fanboy Review

Windows 11 Settings App

Working with Migen(Python) & LiteX | 1 . Setting up Migen

Integration of Git, GitHub, Jenkins and Docker

| Engineering News-Record

Allocations and Eliminations: Oracle Fusion Cloud

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Strong Read on Master-Slave MySQL Setup — Part 1

Importing Mongo Metrics from Atlas to Influx

Neural Architecture Search (NAS)

Engineering Journal: SDC