Compact BST Serialization
Problem
Write encode(root), which turns a binary search tree with distinct whole-number keys into a string, and decode(text), which rebuilds the exact same tree. The string may contain only the keys separated by single spaces, with no markers for missing children, so it is as short as the keys allow. Both functions should run in linear time and should not recurse, because the tree can be as tall as it has nodes.
Examples
Input: tree = 8, left 3 (children 1 and 6), right 10 (right child 14)
Output: encode -> "8 3 1 6 10 14"
decode("8 3 1 6 10 14") rebuilds the same shape
Why: pre-order lists each node before its childrenInput: tree = a chain 1 -> 2 -> 3, each key the right child of the previous one
Output: encode -> "1 2 3"
Why: decode knows 2 cannot be a left child of 1, since 2 is largerInput: tree = empty
Output: encode -> ""
decode("") -> empty tree
Why: edge case, nothing to writeHints
0 / 3
A general tree needs markers for missing children. A search tree does not, because its key order already says where each key has to go.
Write the keys in pre-order. Reading them back, each key is either the left child of the key just before it, or the right child of some earlier key on the path back up.
Decode with a stack of the path from the root. For each new key, pop while the top of the stack is smaller; if anything was popped, the new node is the right child of the last popped node, otherwise it is the left child of the top. Push the new node.
Solution
In pre-order a node comes before its whole subtree, so the first key is the root, and the search order decides everything else. The decoder keeps the path from the root on a stack; a key larger than the stack's top has left that node's left subtree, so nodes are popped until the next one is larger than the new key, and the new key becomes the right child of the last one popped. If nothing was popped, the new key is the left child of the top. Each node is pushed and popped at most once. Time is O(n) for both functions, and space is O(n).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def encode(root):
keys, stack = [], [root] if root else []
while stack: # iterative pre-order
node = stack.pop()
keys.append(str(node.val))
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return " ".join(keys)
def decode(text):
keys = [int(k) for k in text.split()]
if not keys: return None
root = T(keys[0]); path = [root]
for k in keys[1:]:
node, parent = T(k), None
while path and path[-1].val < k: # k has left these nodes' left subtrees
parent = path.pop()
if parent: parent.right = node
else: path[-1].left = node
path.append(node)
return root
tree = T(8, T(3, T(1), T(6)), T(10, None, T(14)))
print(encode(tree)) # -> 8 3 1 6 10 14
print(encode(decode("1 2 3")) == "1 2 3") # -> True
print(decode("")) # -> NoneStuck on the idea rather than the code? Serialize a Tree covers it.