# binary search trees in ECMAScript

I recently came across this article when reading about Binary Search Trees. Although the article is helpful in explaining BSTs, I felt the author's implementation wasn't very idiomatic to JavaScript. I think there are some interesting and important things we can glean from refactoring his code.

Let's refactor! We are beginning with:

```"use strict";

class BinarySearchTree {
constructor() {
//initially root is null

this.root = null;
}

insertNumberNode(data, left = null, right = null) {
//creating a Node
//data we pass will act as individual parent Node
//left and right are subtrees
let Node = {
data,
left,
right
};
//suppose currentNumberNode as a parent node
//current Num Node value decides position of next value
//if it goes to left subtree or right subtree
let currentNumberNode;

if (!this.root) {
//if its not a root make it one by passing a Node
this.root = Node;
} else {
//and if its a root now, assign it to currentNumberNode
currentNumberNode = this.root;
while (currentNumberNode) {
//if data is smaller than cuurent data, send it in left subtree
if (data < currentNumberNode.data) {
//if current num node don't have Node properties
//we will assign it node properties
if (!currentNumberNode.left) {
currentNumberNode.left = Node;
break;
} else {
//if it has node properties and it is sent by root to left
//we will make it a left node because it is smaller than root node
currentNumberNode = currentNumberNode.left;
}
//if data is larger than cuurent data, send it in right subtree
} else if (data > currentNumberNode.data) {
//if current num node don't have Node properties
//we will assign it node properties
if (!currentNumberNode.right) {
currentNumberNode.right = Node;
break;
} else {
//if it has node properties and it is sent by root to right
//we will make it a right node because it is larger than root node
currentNumberNode = currentNumberNode.right;
}
} else {
console.log("Try Different Value");
break;
}
}
}
}
}
let BSTtest = new BinarySearchTree();

//tests

BSTtest.insertNumberNode(10);

BSTtest.insertNumberNode(7);

BSTtest.insertNumberNode(14);

BSTtest.insertNumberNode(5);

BSTtest.insertNumberNode(13);

BSTtest.insertNumberNode(8);

BSTtest.insertNumberNode(18);

BSTtest.insertNumberNode(15);

BSTtest.insertNumberNode(6);

BSTtest;
```
and will get to this:
```"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));

console.log(bst);
```

# class

Let's start with the use of the `class` keyword. This has been a topic of debate ever since it was proposed, because

## JavaScript does not have classes

But it has a `class` keyword which you can use to create objects... So doesn't that mean it has classes? No. From [MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes): > JavaScript classes, introduced in ECMAScript 2015, are primarily syntactical sugar over JavaScript's existing prototype-based inheritance. The class syntax does not introduce a new object-oriented inheritance model to JavaScript. Classes are the basis for classical inheritance, which JavaScript does not support. JavaScript uses prototypal inheritance. I would recommend avoiding the use of the `class` keyword in JavaScript because I believe it can cause confusion for newcomers who would understandably assume that using `class` will create a class. When you're debugging JavaScript, if you go in thinking in terms of classical inheritance, you may run in to problems. Let's refactor this to idiomatic JavaScript. Objects in JavaScript can be instantiated from functions using the `new` keyword, so
```class BinarySearchTree {
...
}

const bst = new BinarySearchTree();
```
becomes
```function BinarySearchTree() {
...
}

const bst = new BinarySearchTree();
```
Pretty much the same thing! It's still a convention to capitalize the function to show it will be used as a prototype for instantiating objects. The `new` keyword will create a new Object with inner state created with the `this` keyword in the function. So, for example, this
```function ShinyObject() {
this.boo = "far";
}

const thing = new ShinyObject();
console.log(thing.boo);
```
will log `far` to the console. In English, `new ShinyObject()` can be read as "please create a new JSON object and then give it to the ShinyObject function, which will refer to it as `this`". Then the ShinyObject function runs, it sets the new object's state with `this.boo = "far";` and you have a nice new `thing` variable that is now equal to `{ boo: "far" }`. Let's make some changes:
```"use strict";

function BinarySearchTree() {

this.root = null;

this.insertNumberNode = function(data, left = null, right = null) {

let Node = {
data,
left,
right
};

let currentNumberNode;

if (!this.root) {
this.root = Node;
} else {
currentNumberNode = this.root;
while (currentNumberNode) {
if (data < currentNumberNode.data) {
if (!currentNumberNode.left) {
currentNumberNode.left = Node;
break;
} else {
currentNumberNode = currentNumberNode.left;
}
} else if (data > currentNumberNode.data) {
if (!currentNumberNode.right) {
currentNumberNode.right = Node;
break;
} else {
currentNumberNode = currentNumberNode.right;
}
} else {
console.log("Try Different Value");
break;
}
}
}
}
}

let BSTtest = new BinarySearchTree();

BSTtest.insertNumberNode(10);
BSTtest.insertNumberNode(7);
BSTtest.insertNumberNode(14);
BSTtest.insertNumberNode(5);
BSTtest.insertNumberNode(13);
BSTtest.insertNumberNode(8);
BSTtest.insertNumberNode(18);
BSTtest.insertNumberNode(15);
BSTtest.insertNumberNode(6);
```
Now that we aren't using the `class` keyword, we don't need a special `constructor` function; we can simply say `this.root = null;`. We also had to modify the `insertNumberNode` function by making it a key on the `this` object and assigning an anonymous function to it: Before:
```insertNumberNode(data, left = null, right = null) {
...
}
```
After:
```this.insertNumberNode = function(data, left = null, right = null) {
...
}
```
That's it! I think the use of the `this` keyword also allows us to think more clearly about the object we're creating: `this.insertNumberNode` clearly shows the object will have a function you will be able to call with `objectName.insertNumberNode()`. Next, let's take a look at those [default parameters](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/Default_parameters) (`left = null, right = null`). He is setting the default value of the `left` and `right` nodes to `null` because when the code inserts a new node, it won't have any children. Coming from other languages, it would make sense to have a set data structure for `node`s. However, in JavaScript, object structures aren't enforced. Instead of creating `{ data: 3, left: null, right: null }` we can just as easily create `{ data: 3 }`. Much simpler! Looking at where he uses `currentNumberNode.left` or `currentNumberNode.right`, changing to this structure should have no effect. Because he is using them as an `if` condition, they will be coerced by the JavaScript engine to be a boolean value. Because something with a `null` value is [falsy](https://developer.mozilla.org/en-US/docs/Glossary/Falsy), his current code will evaluate to `false`. Our new code will do the same, because `undefined` values are also `falsy`. Looks better so far:
```"use strict";

function BinarySearchTree() {

this.root = null;

this.insertNumberNode = function(data) {

let Node = { data };

let currentNumberNode;

if (!this.root) {
this.root = Node;
} else {
currentNumberNode = this.root;
while (currentNumberNode) {
if (data < currentNumberNode.data) {
if (!currentNumberNode.left) {
currentNumberNode.left = Node;
break;
} else {
currentNumberNode = currentNumberNode.left;
}
} else if (data > currentNumberNode.data) {
if (!currentNumberNode.right) {
currentNumberNode.right = Node;
break;
} else {
currentNumberNode = currentNumberNode.right;
}
} else {
console.log("Try Different Value");
break;
}
}
}
}
}

let BSTtest = new BinarySearchTree();

BSTtest.insertNumberNode(10);
BSTtest.insertNumberNode(7);
BSTtest.insertNumberNode(14);
BSTtest.insertNumberNode(5);
BSTtest.insertNumberNode(13);
BSTtest.insertNumberNode(8);
BSTtest.insertNumberNode(18);
BSTtest.insertNumberNode(15);
BSTtest.insertNumberNode(6);
```
Now let's take a look at that those conditional statements within the `while` loop. He is checking if `data < currentNumberNode.data` and doing stuff if it is, then he's checking if `data > currentNumberNode.data` and doing stuff if it is, and then handling every other condition using an `else` statement. Looking inside each `if` block, the code is exactly the same except for the `left` and `right` fields. Let's dry this up a bit:
```"use strict";

function BinarySearchTree() {

this.root = null;

this.insertNumberNode = function(data) {

let Node = { data };

let currentNumberNode;

if (!this.root) {
this.root = Node;
} else {
currentNumberNode = this.root;
while (currentNumberNode) {

if (data === currentNumberNode.data) { throw "NotUnique"; }

const branch = data < currentNumberNode.data ? 'left' : 'right';

if (!currentNumberNode[branch]) {
currentNumberNode[branch] = Node;
break;
} else {
currentNumberNode = currentNumberNode[branch];
}

}
}
}
}

let BSTtest = new BinarySearchTree();

BSTtest.insertNumberNode(10);
BSTtest.insertNumberNode(7);
BSTtest.insertNumberNode(14);
BSTtest.insertNumberNode(5);
BSTtest.insertNumberNode(13);
BSTtest.insertNumberNode(8);
BSTtest.insertNumberNode(18);
BSTtest.insertNumberNode(15);
BSTtest.insertNumberNode(6);

console.log(BSTtest);
```
Instead of accessing object properties with a hardcoded `left` and `right`, we can create a new `branch` variable with a value of either `left` or `right` and then perform the same operations on `currentNumberNode` programatically with `currentNumberNode[branch]`. This not only eliminates the need for writing the inner code twice, but also eliminates the need for the `if` / `else` blocks. The last `else` condition caught all other conditions aside from `data < currentNumberNode.data` and `data > currentNumberNode.data`, which means the only time it would execute is if `data === currentNumberNode.data`. This is because Binary Syntax Trees cannot have two nodes with equal values; every node's value must be unique. Because of this, we can just throw custom exception if they are equal before any other logic with `if (data === currentNumberNode.data) { throw "NotUnique"; }`. Eliminating code is fun! Let's do more. But first, let's rename some things.
```"use strict";

function BinarySearchTree() {

this.root = null;

this.insert = function(data) {

let node = { data };

let current;

if (!this.root) {
this.root = node;
} else {
current = this.root;
while (current) {

if (data === current.data) { throw "NotUnique"; }

const branch = data < current.data ? 'left' : 'right';

if (!current[branch]) {
current[branch] = node;
break;
} else {
current = current[branch];
}

}
}
}
}

let bst = new BinarySearchTree();

bst.insert(10);
bst.insert(7);
bst.insert(14);
bst.insert(5);
bst.insert(13);
bst.insert(8);
bst.insert(18);
bst.insert(15);
bst.insert(6);

console.log(bst);
```
`Node` and `BSTtest` shouldn't be capitalized because that implies they will be used as a prototypes, which they are not. I also shortened `insertNumberNode` to `insert` since it should be obvious all nodes are numbers. Next, let's take a look at
```current = this.root;
while (current) {
...
}
```
The `while` loop will coerce the conditional expression into a boolean. Because `current` is always equal to `this.root`, which is an object, it will always be [truthy](https://developer.mozilla.org/en-US/docs/Glossary/Truthy); it makes more sense to just create a loop with `while (true)`. The `current` variable is also instantiated above the blocks where it's used, which isn't necessary; `let current;` can be removed and `current = this.root;` changed to `let current = this.root;`. Let's make these changes as well as add the NodeJS `util` module to let us log the entire Binary Search Tree object to the console.
```"use strict";

function BinarySearchTree() {

this.root = null;

this.insert = function(data) {

let node = { data };

if (!this.root) {
this.root = node;
} else {
let current = this.root;
while (true) {

if (data === current.data) { throw "NotUnique"; }

const branch = data < current.data ? 'left' : 'right';

if (!current[branch]) {
current[branch] = node;
break;
} else {
current = current[branch];
}

}
}
}
}

let bst = new BinarySearchTree();

bst.insert(10);
bst.insert(7);
bst.insert(14);
bst.insert(5);
bst.insert(13);
bst.insert(8);
bst.insert(18);
bst.insert(15);
bst.insert(6);

const util = require('util');
console.log(util.inspect(bst, false, null, true));
```
He is originally setting `this.root = null;` then creating a `node` object with `let node = { data };`, then checking if `this.root` exists and sets `this.root = node;` if it doesn't. We can easily inline these assignments with `this.root = { data }`. Let's do this and convert that normal anonymous function to an [arrow function](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/Arrow_functions):
```"use strict";

function BinarySearchTree() {

this.root = null;

this.insert = data => {

if (!this.root) {
this.root = { data };
} else {
let current = this.root;
while (true) {

if (data === current.data) { throw "NotUnique"; }

const branch = data < current.data ? 'left' : 'right';

if (!current[branch]) {
current[branch] = { data };
break;
} else {
current = current[branch];
}

}
}
}
}

let bst = new BinarySearchTree();

bst.insert(10);
bst.insert(7);
bst.insert(14);
bst.insert(5);
bst.insert(13);
bst.insert(8);
bst.insert(18);
bst.insert(15);
bst.insert(6);

const util = require('util');
console.log(util.inspect(bst, false, null, true));
```
Let's also update `BinarySearchTree` to take an initial node value upon instantiation. A Binary Search Tree needs at least one node, so it makes sense to set this right away instead of initializing `this.root` as `null`. Because `this.root` will always be set now, we can remove the `if` block and also move its declaration as a default parameter of `this.insert()`. Let's also rename `data` to `n` since `data` is a bit ambiguous and because `n` is a common and succinct name for an integer.
```"use strict";

function BinarySearchTree(n) {

this.root = { n };

this.insert = (n, current = this.root) => {

while (true) {

if (n === current.n) { throw "NotUnique"; }

const branch = n < current.n ? 'left' : 'right';

if (!current[branch]) {
current[branch] = { n };
break;
} else {
current = current[branch];
}

}
}
}

let bst = new BinarySearchTree(10);

bst.insert(7);
bst.insert(14);
bst.insert(5);
bst.insert(13);
bst.insert(8);
bst.insert(18);
bst.insert(15);
bst.insert(6);

const util = require('util');
console.log(util.inspect(bst, false, null, true));
```
# Recursion! We can tighten the code up a bit and make it work a little more declaratively by turning `insert` into a recursive function. As the function recurses through the tree, it will need to keep track of two pieces of state: both `n` and the `current` node it is looking at. Refactor!
```"use strict";

function BinarySearchTree(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 };
}

}

}

let 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));
```
The conditional logic changed a bit: it now says "if the current node contains a branch (`left` or `right`) where it should normally put `n`, then call `this.insert` on that branch. If that branch doesn't exist yet, then create one and set it equal to an object with the input number as its value." I also changed the logic for creating the test tree; instead of hardcoding multiple calls to `insert()`, we can just use `Array.forEach` to iterate through an array of values we want to insert. # Hoisting JavaScript will hoist variables declared with `var` and functions to the top of their scope. This is not a good thing. Luckily, we can prevent this with `const` and `let`, which JavaScript does not hoist:
```"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));
```
Using `const` to assign a function to an immutable variable is a great idea for reasons other than the prevention of hoisting. It's a great idea to have everything immutable by default, but that's outside the scope of this article. # Const There's one more small change in the last iteration of our code:
```let bst = new BinarySearchTree(10);
```
is now
```const bst = new BinarySearchTree(10);
```
But aren't we mutating `bst` with `bst.insert()`? Yes and no! What? Unlike some other languages, when we declare `const bst` and assign it a value, JavaScript does not make the entire object immutable. In JavaScript, object literals are passed my reference, not by value; the thing that is a constant is the reference to the object, not the object itself. That means you can do:
```const myObj = { kung: "fu" };
myObj.kung = "foo";
```
and that will work just fine.

# we're done!

I hope this tutorial was helpful for you! If you have any questions or input on anything which could be improved, feel free to let me know.