DEV Community

BillyGoat12
BillyGoat12

Posted on • Updated on

Javascript tree explained!!

What is a Tree?

A tree in Javascript is a data structure made of nodes which are nested into each other. A node is typically an object that contains a value and a nested child node. This data structure is arranged in order of rank according to its value.

This data structure is important because binary search can be easily used in it. According to Wikipedia, a binary search is a "search algorithm" that will improve the efficiency of our code by reducing input required for the next iteration when looping through the data. It does that by "compares the target value to the middle element of the data structure".

adding node to the tree

step 1: When adding nodes to the tree you will have to check if the current node has a value that is greater or less then the value you are trying to add to the tree. Step 2: If the value is greater then the value you want to add, then you will have to check if the node at the left has a value, otherwise check the right. Step 3: If it does not have a value, then set it to the value you are adding, otherwise go into that node and repeat the process all over again.

Here is an example of what your insert function would look like!

Alt Text

when iterating through the tree

You will have to check if the current value is the value you want and if so return true. Check if the current value is undefined and if so return false. otherwise, you will have to check if the value is greater or less then the value you are trying to access from the tree. If the value is greater then the value you want to access, then you will have to check if the node at the left has a value, otherwise check the right. If it does not have a value, then return false, otherwise go into that node and repeat the process all over again.

Here is an example of what your contains function would look like!

Alt Text

Here is an example of tree data structure using binary search!!

Alt Text
This picture is from:(https://www.guru99.com/binary-search-tree-data-structure.html)

More about this picture

As you can see that it is the goal of the tree data structure is to have the median value at the very top of the tree this will help your function to access the child node based on greater than and less then that value.

One problem we may face when using the tree data structure.

One problem we may face is when the order of rank according to value is not in the correct order. To fix this you will have to re-balance the tree by adding complexity to your insert and remove code. Even though your add and remove code will increase in complexity, the complexity of the code required to sort through the data will be halved. You could also just reset the tree and re-balance it accordingly.

Conclusion

Binary search tree is one of the many data structures to choose from when building your data. This data structure comes with its advantages and disadvantages, but when used correctly can be very powerful.

Top comments (0)