Build a tree class from level-order arrays with height and mirror
An interview-prep site stores every binary tree exercise as a compact level-order array, like [5, 3, 8, 1, 4, null, 9]. Its tree visualizer needs a small class that turns that array into a real tree and answers the questions the exercises ask: how big, how tall, what order, is it balanced, and what does its mirror image look like.
Implement a class BinaryTree.
const tree = new BinaryTree(values = []);
tree.size() // => number of nodes
tree.height() // => nodes on the longest root-to-leaf path (0 when empty)
tree.traverse(order) // => array of values
tree.leaves() // => values of the leaves, left to right
tree.isBalanced() // => boolean
tree.mirror() // => a new BinaryTree, flipped left to right
tree.toArray() // => level-order array in the same format as the input
values[0] is the root. The next entries give the children of each existing node in breadth-first order: left child, then right child, then the next node’s two children, and so on.null (or undefined) means “no child here”. Missing nodes have no children, so no entries are listed for them.null, is an empty tree. Values are never null or undefined, but can be any other value (numbers, strings).traverse(order) returns values in one of these orders: 'preorder' (node, left, right), 'inorder' (left, node, right), 'postorder' (left, right, node) or 'levelorder' (breadth-first, each level left to right). Any other order throws an Error.mirror() returns a new BinaryTree in which every node’s left and right children are swapped. The original tree does not change.toArray() returns the tree in the level-order format with no trailing nulls. Feeding the result back into new BinaryTree(...) gives the same tree. An empty tree returns [].values array passed to the constructor.// 5
// / \
// 3 8
// / \ \
// 1 4 9
// \
// 2
const tree = new BinaryTree([5, 3, 8, 1, 4, null, 9, null, 2]);
tree.size(); // => 7
tree.height(); // => 4
tree.traverse('preorder'); // => [5, 3, 1, 2, 4, 8, 9]
tree.traverse('inorder'); // => [1, 2, 3, 4, 5, 8, 9]
tree.traverse('postorder'); // => [2, 1, 4, 3, 9, 8, 5]
tree.traverse('levelorder'); // => [5, 3, 8, 1, 4, 9, 2]
tree.leaves(); // => [2, 4, 9]
tree.isBalanced(); // => true
tree.toArray(); // => [5, 3, 8, 1, 4, null, 9, null, 2]
tree.mirror().toArray(); // => [5, 8, 3, 9, null, 4, 1, null, null, null, null, 2]
tree.mirror().traverse('inorder'); // => [9, 8, 5, 4, 3, 2, 1]
new BinaryTree([1, 2, null, 3]).isBalanced(); // => false
new BinaryTree().height(); // => 0
new BinaryTree([null]).toArray(); // => []