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:
- 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 toBinarySearchTree
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.