joyful linux

Let's expand on our previous work with Binary Search Trees by adding an invert() method. Note: These articles are meant as resources for education on JavaScript, not algorithms. Implementing these algorithms in JavaScript will allow us to do a deep dive into how certain aspects of the language works. We left off with this implementation: "use strict"; const BinarySearchTree = function(n) { this.root = { n }; this.insert = (n, current = this.root) => { if (n === current.n) { throw "NotUnique"; } const branch = n < current.n ? 'left' : 'right'; if (current[branch]) { this.insert(n, current[branch]); } else { current[branch] = { n }; } } } const bst = new BinarySearchTree(10); [7, 14, 5, 13, 8, 18, 15, 6].forEach(x => bst.insert(x)); const util = require('util'); console.log(util.inspect(bst, false, null, true)); I want to be able to call bst.invert() to produce a new BST object that is inverted (i.e. what was on the right is now on the left, and vice versa). However, I don't want to mutate the original BST. I want invert() to produce a clone of bst. Before we get to that, let's implement invert() in a mutable way. "use strict"; const BinarySearchTree = function(n) { this.root = { n }; this.insert = (n, current = this.root) => { if (n === current.n) { throw "NotUnique"; } const branch = n < current.n ? 'left' : 'right'; if (current[branch]) { this.insert(n, current[branch]); } else { current[branch] = { n }; } } this.invert = (current = this.root) => { if (current.left || current.right) { const l = current.left; current.left = current.right; current.right = l; } if (current.left) { this.invert(current.left); } if (current.right) { this.invert(current.right); } } } const bst = new BinarySearchTree(10); [7, 14, 5, 13, 8, 18, 15, 6].forEach(x => bst.insert(x)); const util = require('util'); console.log(util.inspect(bst, false, null, true)); console.log('\nINVERTING! \n'); bst.invert() console.log(util.inspect(bst, false, null, true));