CODEX
Traversing a Forest of Data
All About Binary Search Trees in Javascript
Structural Integrity
Programming and data storage go hand-in-hand. There are many different schools of thought in regards to which data structures are considered to be best. ‘Best’, in this context, usually relates to the time complexity of the structure, or how long it will take the interpreter to either manipulate or locate the individual pieces of data within the storage. Since computers can only run a finite amount of actions, within a set amount of time, efficiency is the ‘name-of-the-game’ when writing code. Efficiency can come in many forms, but in terms of data structures, there are three main concerns when considering the time complexity of acting upon the data within. These include the traversal of the data, the deletion of pieces of data, and the insertion of new pieces of data, all of which take place within the structure.
Binary Search Tree
One widely used type of data structure is a Binary Search Tree, which will be referred to as a BST from hereon in. It can be quickly deduced from their name that BSTs are tree-like structures, meaning they are non-linear. In other words, tree-like structures have nodes, or instances, that branch off of each other. The associations between nodes within a BST are referred to as parent/child relationships. Furthermore, when a parent has two child nodes, the children nodes’ bond can be called a sibling relationship. These two children are often referred to as the left child and the right child. As is the case in most human families, the children are treated very differently from one another. This will be further explored in the sections below.
Key Principles
BSTs have a few key principles, which both define situations in which they should be used, and differentiate them from other data storage techniques. In no particular order:
- Each piece of data must be distinct from all other pieces of data, meaning it can exist only once.
- Each node can have either 0, 1, or 2 children.
- Aside from the very last nodes in a BST, (also called leaf nodes), every node will have two children.
- The very first node, or root node, is the first value used when comparing values and deciding what steps to take next.
- The left child’s value will always be less than its parent node’s value, while the right child’s value will always be greater than its parent node’s value.
When searching for, adding, or removing in a BST, a binary search is used. This means that the interpreter will compare a value to the root node; if it is greater than the root’s value, the focus will shift to the right child, and if it is less than the root’s value, the left child will be looked towards. This continues until, either the interpreter’s goals are complete, or until it reaches the leaf node. Essentially, this means that the amount of data that must be processed is cut in half after each comparison, which is beneficial to the time complexity of the data structure.
Main Methods
BSTs, or any data storage method for that matter, are tools to be utilized. In order for them to actually be useful for real-world application, they must do three main actions: traversal, insertion, and deletion of the data stored within. BSTs will often have an action method (depthFirstLog(callback)) which accepts a callback function and passes each piece of data through it. They also normally have a contains method (contains(value)), and an insertion method (insert(value)), each of which accepts a value as the only parameter. The deletion method is sometimes included. When implementing a BST, a node constructor is also used in order to create a new BST instance. It is used congruently with the methods to create the final product, a BST. The implementation of a BST creating function will look similar to this:
const BinarySearchTree = (value) => {var BST = Object.create(BinarySearchTree.prototype);BST.value = value;
BST.right = null;
BST.left = null;return BST;};
As you can see, both the right and left nodes are initialized with values of null. Null will always be transferred to the leaf nodes, so that when accessing values within the BST, null will be the base case, meaning the recursing will cease once it reaches a node with the value of null.
Next, the methods can be added to the prototype of the constructor function:
// Insert //
BinarySearchTree.prototype.insert = (value) => {
};// Contains //
BinarySearchTree.prototype.contains = (value) => {
};// Depth First Log //
BinarySearchTree.prototype.depthFirstLog = (callback) => {
};
Insert
The insert method will accept a value, which is to be added to an existing BST. First, it will check if the tree is empty. If it is, it will create a new tree, placing the passed-in value inside the root node. If the tree is not empty, however, the method will compare the value passed into it with the root’s value. If it is greater than the root’s value, it will look toward the root’s right child. If it is less than the root’s value, it will look toward the root’s left child. This will continue until either the right or the left child no-longer exists, at which point the new value will be added to the tree.
Time Complexity — linear( O(n) ); average case: O(log n)
Contains
The contains method will traverse the BST in the same manner as the insert method. It will compare to root, and move left or right accordingly. The main difference between the two methods is that insert manipulates the BST and returns nothing, while contains simply looks into the BST and returns a boolean value, based on whether or not it was able to locate the passed-in value within the BST.
Time Complexity — linear( O(n) ); average case: O(log n)
Depth First Log
The depthFirstLog method must behave differently than contains and insert. This is due to its nature; since actions must be taken on all of the values within the BST, the interpreter cannot simply perform a binary search. Instead, it must go down each branch, pass the values into the callback function, then move back up the branch, and down its sibling. This will continue until it reaches the very end of the tree. In order to move down, and then back up a branch, recursion should be used for this method’s implementation.
Time Complexity — linear( O(n) ); average case: O(log n)
Binary search trees are extremely useful forms of data storage structures. They can maintain a reasonable time complexity when accessing the data stored within. They are especially applicable if dealing with a large amount of data, that must be recalled, and/or traversed relatively quickly. Most programmers would greatly benefit from mastering the art of Binary Search Trees.
References:[1]: Pawar, Prakash. “How Binary Search Trees Work in JavaScript - JavaScript in Plain English.” Medium, Javascript in Plain English, 7 Feb. 2019, js.plainenglish.io/binary-search-tree-in-javascript-ca5aa7ba05de.Further Reading:- Hall, Joshua. “Binary Search Trees Through JavaScript.” DigitalOcean, 23 Jan. 2021, www.digitalocean.com/community/tutorials/js-binary-search-trees.- Han, Tim. “JavaScript: What Is a Binary Search Tree? - JavaScript in Plain English.” Medium, Javascript in Plain English, 11 Apr. 2019, js.plainenglish.io/javascript-what-is-a-binary-search-tree-a602155abae4.- Jay. “Detailed Binary Search Tree Guide in JavaScript.” The Coding Delight, 27 Mar. 2019, www.thecodingdelight.com/binary-search-tree-implementation-javascript.- Mejia, Adrian. “Tree Data Structures in JavaScript for Beginners.” Adrian Mejia Blog, 23 May 2019, adrianmejia.com/data-structures-for-beginners-trees-binary-search-tree-tutorial.- Mitrakos, Michael. “Implement a Binary Search Tree in JavaScript - InitJS.” Medium, 23 Feb. 2020, initjs.org/implement-a-binary-search-tree-in-javascript-952a44ee7c26.- Pawar, Prakash. “How Binary Search Trees Work in JavaScript - JavaScript in Plain English.” Medium, Javascript in Plain English, 7 Feb. 2019, js.plainenglish.io/binary-search-tree-in-javascript-ca5aa7ba05de.- Zakas, Nicholas. “Computer Science in JavaScript: Binary Search Tree, Part 1.” Human Who Codes, 9 June 2009, humanwhocodes.com/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1.
