Implement a Binary Search Tree in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital, I write about tech topics and teach…

Implement a Binary Search Tree in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital, I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

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.

Analysis of a Binary Search Tree

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.

Methods of a Binary Search Tree

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.

Let’s dive deeper into the BST methods

Insert

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.

Contains

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

Depth First Log

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!

Pseudocode for a Binary Search Tree

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.

Create BST constructor define value, right child and left child

 Create new node with passed in value
 Create recursive function
 If current node value > value && left child is undefined
 Insert node as left child
 If current node value > value
 Recurse current node left child
 If current node value <value && right child is undefined
 Insert node as right child
 If current node value <value
 Recurse current node right child
 Call recursive function on root node

 Create variable to hold found node
 Create recursive function
 If current node value is equal to value
 Set variable equal to true
 else if BST left child is !undefined && value < BST value 
 recurse with current node's left child
 else if BST right child is !undefined && value > BST value
 recurse with current node's right child
 Call recursive function on root node
 Return variable of found node

 Create recursive function
 Use call with callback on BST and BST value
 If left child is not undefined 
 Recurse through left child
 If right child is not undefined
 Recurse through right child
 Call recursive function on root node

Time complexity of a Binary Search Tree

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(logn).

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

When is Binary Search Tree useful

When it comes to efficiently organizing and retrieving data, Binary Search Trees (BSTs) are a valuable tool in JavaScript programming. BSTs are especially useful when dealing with large datasets and performing operations such as searching, inserting, and deleting elements. The key advantage of BSTs lies in their ability to store and retrieve data in logarithmic time complexity, making them highly efficient for applications that require fast access and manipulation of data. The structure of a BST allows for easy sorting and searching, as each node in the tree holds a key value and has two child nodes, one on the left and one on the right, following a specific ordering principle. This ordering principle ensures that the left child node always holds a smaller value than the parent node, while the right child node holds a larger value. By leveraging this property, BSTs enable efficient searching and traversal operations, making them a popular choice for implementing algorithms like binary search, which significantly reduces the number of comparisons needed to find a specific element within the tree. In JavaScript, BSTs can be implemented using objects or classes, providing a flexible and powerful data structure for a wide range of applications.

Code

JavaScript eBook

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

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

Interview questions regarding binary search trees

Design an algorithm to find a path from one node in a binary tree to another

Start by initializing an empty path to store the nodes in the path from the source node to the target node.
Perform a depth-first search starting from the root of the binary tree.
At each node visited during the DFS traversal, add the current node to the path.
Check if the current node matches the source node or the target node. If it matches either of them, stop the traversal and return the path.
If the current node does not match the source or target node, recursively explore the left and right child nodes.
If both the left and right child nodes return a null path (indicating that neither of them contains the source or target node), remove the current node from the path.
After the DFS traversal finishes, return the path.

Given a binary tree, check whether it’s a binary search tree or not

Start by defining a helper function that takes in a node, along with a minimum and maximum value range.
In the helper function, check if the current node is null. If so, return true since an empty tree is considered a valid BST.
Check if the value of the current node is within the specified range of minimum and maximum values. If not, return false.
Recursively call the helper function for the left child node, updating the maximum value as the value of the current node (since all values on the left subtree must be less than the current node’s value).
Recursively call the helper function for the right child node, updating the minimum value as the value of the current node (since all values on the right subtree must be greater than the current node’s value).
If both recursive calls return true (indicating that the left and right subtrees are valid BSTs), return true; otherwise, return false.

Find the minimum depth of binary search tree

Start by checking if the root node of the BST is null. If it is, return 0 since there are no nodes in the tree.
Check if both the left and right child nodes of the root are null. If they are, return 1 since the root node itself is the only node in the tree.
If either the left child or right child is null, recursively find the minimum depth of the non-null child and add 1 to account for the current level.
If both the left and right child nodes are not null, recursively find the minimum depth of both subtrees and take the minimum of the two depths. Add 1 to account for the current level.
Return the minimum depth obtained from the above steps.

Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k

Start with the root node of the BST.
Initialize two variables: closestNode to keep track of the closest node found so far, and minDiff to keep track of the minimum difference between the node values and the target value k. Set closestNode initially to the root node and minDiff to the absolute difference between the value of the root node and k.
Traverse the BST iteratively using a while loop until reaching a leaf node or finding an exact match for k.
Inside the loop, compare the absolute difference between the current node’s value and k with minDiff. a. If the difference is smaller than minDiff, update minDiff with the new minimum difference and update closestNode to the current node. b. If the current node’s value is equal to k, return the current node as it is an exact match.
If the target value k is less than the current node’s value, move to the left child of the current node.
If the target value k is greater than the current node’s value, move to the right child of the current node.
Continue the loop until reaching a leaf node or finding an exact match.
After the loop ends, return the closestNode as the node in the BST that is closest to the given value k.

Create new node with passed in value Create recursive function If current node value > value && left child is undefined Insert node as left child If current node value > value Recurse current node left child If current node value <value && right child is undefined Insert node as right child If current node value <value Recurse current node right child Call recursive function on root node Create variable to hold found node Create recursive function If current node value is equal to value Set variable equal to true else if BST left child is !undefined && value < BST value recurse with current node's left child else if BST right child is !undefined && value > BST value recurse with current node's right child Call recursive function on root node Return variable of found node Create recursive function Use call with callback on BST and BST value If left child is not undefined Recurse through left child If right child is not undefined Recurse through right child Call recursive function on root node