Serialize and parse binary trees in level-order format
An interview-practice site stores the binary trees used in its exercises as short strings in the database, and its tree viewer turns them back into nodes. Both sides must agree on one exact text format, so that strings written by hand in the admin panel load correctly too.
Build treeCodec, an object with two methods:
treeCodec.serialize(root) // => string
treeCodec.deserialize(text) // => root node, or null
A node is a plain object { value, left, right }. value is an integer (it can be negative or zero), and left and right are nodes or null. An empty tree is null.
#. Children of a missing child are not listed.# at the end of the list, then join the entries with ,. No spaces.-12.''.serialize must produce exactly this format, and must not modify the tree.deserialize accepts any string in this format, including ones written by hand. It returns new node objects with exactly the keys value, left and right. Values are numbers, and missing children are null.deserialize(serialize(root)) is a tree with the same shape and values.// 8
// / \
// 3 10
// \ \
// 6 14
treeCodec.serialize(root); // => '8,3,10,#,6,#,14'
// 1
// /
// 2
treeCodec.serialize(oneLeft); // => '1,2' (the trailing '#' are removed)
// 1
// \
// 2
// \
// 3
treeCodec.serialize(chain); // => '1,#,2,#,3'
treeCodec.serialize(null); // => ''
const tree = treeCodec.deserialize('-4,0,#,7');
// => { value: -4,
// left: { value: 0, left: { value: 7, left: null, right: null }, right: null },
// right: null }
treeCodec.deserialize(''); // => null