Rebuild a binary tree from inorder and postorder arrays
A collaborative outline editor syncs its document tree to the server as two flat arrays: the inorder and the postorder traversal of a binary tree. Flat arrays are cheap to diff and send. When a client loads a document, it has to rebuild the tree from them. Payloads can be corrupted in transit, so the client must also refuse traversals that do not describe a real tree.
Implement buildTree(inorder, postorder). It returns the root of the binary tree whose traversals are inorder and postorder.
buildTree(inorder, postorder) // => { value, left, right } | null
{ value, left, right }. left and right are nodes or null.===.null when both arrays are empty.Error if the input cannot describe exactly one tree:
inorder contains a duplicate value (then the tree would be ambiguous),postorder is missing from inorder, orinorder = [1, 2, 3] and postorder = [3, 1, 2].// 'doc'
// / \
// 'intro' 'body'
// / \
// 'p1' 'p2'
buildTree(['intro', 'doc', 'p1', 'body', 'p2'], ['intro', 'p1', 'p2', 'body', 'doc']);
// => {
// value: 'doc',
// left: { value: 'intro', left: null, right: null },
// right: {
// value: 'body',
// left: { value: 'p1', left: null, right: null },
// right: { value: 'p2', left: null, right: null },
// },
// }
buildTree([3, 2, 1], [3, 2, 1]);
// => 1 with left child 2, whose left child is 3 (a left-leaning chain)
buildTree([], []); // => null
buildTree([1, 2], [1]); // throws (different lengths)
buildTree([1, 2, 3], [3, 1, 2]); // throws (impossible order)