Data Structures

September 22, 2016

This is the third of a series of articles on implementing data structures in JavaScript. If you’re new to data structures, be sure to start from the beginning with Stacks.

A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children. A BST supports several methods common to any search tree such as contains, insert and depthFirstLog, and delete. We’ll get more into those later on! There are two main ways of representing a BST. I’m going to focus on the method using node objects that have references to their children.

As the name suggests, a BST is just a *binary tree*, only with the following restrictions placed on where nodes can go.

- For each node (
*node1*), every value found in the left sub-tree of*node1*is less than or equal to the value found in*node1*. - For each node (
*node1)*, every value found in the right sub-tree of*node1*is greater than or equal to the value found in*node1*.

That’s not so hard to visualize, but let me reiterate. A BST is just a tree where each left child has a value that’s less than the the parent’s value, and a right child that has a value that’s greater than or equal to the parent’s value.

BSTs have four main methods:

**insert(value)**: Accepts a value and places in the tree in the correct position.**contains(value)**: Accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.**depthFirstLog(callback)**: Accepts a callback and executes it on every value contained in the tree.

*and sometimes contains:*

**delete(value)**: Accepts a value and deletes that specific value within the BST.

The insert method performs binary search on the root node, moving to the left child if *n *is less than the current node or right if *n *is greater than the current node. This continues until the left or right child does not exist, which is where the new node will then be inserted.

The search operation performs binary search much like the insert operation to determine whether *n *exists.

The depthFirstLog method accepts a callback and applies the callback to each value in the BST. This means we need (*should) *recursion to traverse down each BST to apply the callback function to each node.

If you don’t feel comfortable with recursion, I highly suggest you read this article and take some time to practice every day. You’ll be using recursion to solve complex problems a lot more than you might think!

The pseudocode for this is very complex and in detail as I didn’t want to skimp on each line, so take the time to slowly go through each and understand what’s going on.

If you don’t know much about time complexity, take some time and go learn the basics before you move forward.

Methods on a BST always start at the root node and work their way down, due to this, the maximum time each operation takes is based on how high the tree is. For example a tree with *n* nodes where there are no right children will take *O*(*n*) time, a complete BST however (every level except the last is completely filled, with nodes on the last as left as possible) has the worst case time of *O*(log*n*).

- delete: Linear —
, or O(log n) in average case*O(n)* - insert: Linear —
, or O(log n) in average case*O(n)* - contains: Linear —
, or O(log n) in average case*O(n)* - depthFirstLog: Linear —
, or O(log n) in average case*O(n)*

Having worked across sites raking in over 50 billion website visits annually, *Michael Mitrakos** can help your business to crush the web game with an award winning website.*

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!