# Data Structures: Binary Search Trees Explained

Binary search trees allow us to efficiently store and update, in sorted order, a dynamically changing dataset. When binary search trees are balanced, average time complexity for insert and find is `O(log n)`, which is very efficient as our dataset grows. Before we dive into the details of a binary search tree, let’s first quickly review trees. What are trees?

Trees are nonlinear data structures composed of nodes that hold data. These nodes are connected by edges that define a parent and child relationship. Trees are nonlinear in that they are not organized sequentially, instead they are organized through relationships or hierarchy. The first node of a tree is called the root node and it can have zero or more child nodes. A child node in a tree forms a subtree, where that child can have zero or more child nodes of its own, and so on (as you can see there’s a recursive approach to trees). To better visualize what a tree is you can think of a tree as a hierarchical org chart of a company, an animal classification tree in biology, or the Document Object Model (DOM).

What is a binary tree?

There are multiple types of trees, but we will focus on the binary tree. A binary tree is a type of tree in which each node has a maximum of two children. Binary trees can be:

• full: every node has either zero or two children. Nodes do not have only one child.
• complete: every level in the tree is fully filled with the possible exception of the last level, which should be filled from left to right.
• perfect: it is both full and complete and must have exactly 2^(n -1) nodes.

What is a binary search tree?

A binary search tree (BST) is a type of binary tree where every node follows a particular ordering property. This ordering property is true for all nodes `n` and it states that all left descendants <= n < all right descendants. What defines a node as less than or greater than another node depends on your data type.

As mentioned earlier, its time complexity has an average of `O(log n)` for insert and find as you need not go through each node in the tree. You can divide and conquer by leveraging subsets of the tree. For example, if we want to `insert(19)`into the following BST:

1. We will compare 19 to our root node. As 19 < 20, we can ignore all nodes to the right of our root.

2. Then 19 > 16 so we can ignore all nodes to the left of 16.

3. Finally 19 > 17 and 17 has zero children so we can add 19 to the right of 17.

Coding our binary search tree

Given that we now understand how BSTs work, let’s implement one in JavaScript. As stated earlier, a BST has a max of two children where one child is to the left of (less than) and one is to the right of (greater than) their parent.

We will build our BST with the use of a constructor, which is an object type that is leveraged to create many objects of the same type. A constructor will allow us to create multiple BSTs with the same properties and methods, which is very useful for creating our subtrees.

`function BinarySearchTree (val) {  this.value = val;  this.left = null;  this.right = null;}`

Our BST takes in one parameter, `val`, and when called with the `new` keyword it will assign the received parameter to the `value` property of the current instance. The current instance will have a `left` and `right` property, which will hold the nodes that are less than or greater than itself (in other words, its children). The `left` and `right` properties will eventually be assigned to`BinarySearchTree` instances.

Inserting a Node

Now that we have our BST constructor, let’s work on a simple method (no error handling) that will allow us to insert nodes into our tree. We will assume that we will not have any duplicates to insert. We will leverage our object’s prototype to define our methods in order to save memory. This means that all objects created from this constructor will point to one common prototype object; hence, we only store each method once in memory.

`BinarySearchTree.prototype.insert = function (value) {  let subtree = value < this.value ? 'left' : 'right';  if (this[subtree]) {    this[subtree].insert(value);  } else {    this[subtree] = new BinarySearchTree(value);  }};`

The insert method takes in a value as a parameter, which is the `value` that we’re interested in adding to our tree. We use a ternary operator (we can also leverage an `if` statement) to compare the `value` passed in with our current node. At this stage, our current node is our root. For example, if we run `let newTree = new BinarySearchTree(20)`, then when we run our insert method `newTree.insert(25)` our initial `this.value` will be equal to `20` (our root’s `this.value`). Since our `value` passed in is greater than `this.value`, `subtree` is evaluated to `'right'` and we now know which direction to take in our tree.

We then check if our `this['right']`, which is equivalent to `this.right`, holds a truthy or falsy value. We evaluate it to `false` as `this.right = null`, which is falsy, and then we execute our `else` statement. Our `else` statement will assign `this.right` to a new instance of our BST, which will enable us to create a subtree with its own `left` and `right` properties.

Our tree now holds two nodes, let’s now add a third with the value of `21` by executing `newTree.insert(21).` The `subtree` variable in the `insert` method will be assigned `'right'`, but this time we will execute our block of code in our `if` statement (not our `else` statement) because `this['right']` evaluates to `true` since `this.right` is no longer `null` (it's pointing to the `25`’s node). We will now recurse by calling `insert` on `25`’s node (we will continue to recursively compare `21` to every node until the `if` statement hits a falsy value, meaning our node’s `this.right` or `this.left` value is equal to `null`). When we recurse, `this.value` is equal to `25` and `subtree` is assigned `'left'` as `21` < `25`. We will then execute our code in our `else` statement as `25`’s `this.left` is `null` and create a new instance of BST with `this.value = 21`.

Finding a Node

Determining if a node exists in our BST is very similar to our `insert` method. We want to recursively evaluate our value passed in against the value of our current node. Let’s call our method `contains` , which will return `true` if the value exists or `false` if it does not exist in our tree. The method will be simple and we will not account for error handling. Please see the below image for a step by step walkthrough of the `contains` method.

`BinarySearchTree.prototype.contains = function (value) {  if (value === this.value) {    return true;  }  let subtree = value < this.value ? 'left' : 'right';  if (this[subtree]) {    return this[subtree].contains(value);  } else {    return false;  }};`

We’ve now implemented a BST with `insert` and `contains` methods in JavaScript! Some additional methods that we can implement are `delete`, `min`, and `max`. These methods would be able to remove nodes from a tree and find the minimum and maximum values of a tree.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.