Binary Tree | Javascript | Part-6.2

Introduction article to the data structure. Binary Tree concept with practical examples applied to the Javascript language.

Are you looking to improve your fundamental knowledge of computer science, especially data structure and algorithms? Then you’re in the right place. Let’s go through some common data structures and implement them in JavaScript.

Binary trees are a type of tree in which each node has a maximum of two children. Each node has a maximum of two nodes with the left node being smaller than the current node and the right node being bigger than the current node.

A binary tree

One key situation in which binary trees are really useful is in searching. And for searching, a certain type of binary tree is used, called binary search trees (BSTs).

BSTs are just like binary trees but information within them is ordered in a way that makes them a suitable data structure for searching.

In BST, values are ordered so that each node that descends to the left side of its parent must have a value less than its parent, and each node that descends to the right side of its parent must have a value bigger than its parent.

This order in its values makes this data structure great for searching since on every level of the tree we can identify if the value being looked for is greater or less than the parent node, and from that comparison progressively discard roughly half of the data until we reach our value.

When inserting or deleting values, the algorithm will follow the following steps:

• Check if there’s a root node.
• If there is, check if the value to add/delete is greater or smaller than the node.
• If it is smaller, check if there is a node to the left and repeat the previous operation. If there’s not, add/remove the node in that position.
• If it is greater, check if there is a node to the right and repeat the previous operation. If there’s not, add/remove the node in that position.

Searching in BSTs is very similar, only instead of adding/deleting values, we check the nodes for equality with the value we’re looking for.

COMMON METHODS OF BINARY SEARCH TREE IN JAVASCRIPT

• add: Insert a node into the tree.
• findMin: Get the minimum node.
• findMax: Get the maximum node.
• find: Search a specific node.
• isPresent: Determine the existence of a certain node.
• remove: Delete a node from the tree.

Add BT BST will have a separate blog

An implementation of a BST might look like this:

The big O complexity of these operations is logarithmic (log(n)). But it’s important to recognize that for this complexity to be achieved, the tree must have a balanced structure so that in each search step, approximately half of the data can be “discarded”. If more values are stored on one side or another of three, the efficiency of the data structure is affected.

Here is the list of Leetcode questions related to the binary tree
https://leetcode.com/problemset/all/?topicSlugs=binary-tree&page=1

Some Leetcode questions can be solved using a hash. Please have a look so you have a clear picture of your mind about the hash data structure.

Leetcode Solutions | Platform for learning to code

Recent Articles if you guys want to checkout

Tree | Javascript | Part-6.1

Hash Table | Javascript | Part-5

Set | Javascript | Part-4

In this blog, I have tried to collect & present the most important points to consider when building Javascript / Node.js applications, feel free to add, edit, comment, or ask.
I recommend you to go over the references for more details. Happy coding!