Write your own Binary Search Tree Implementation in JavaScript

Hello and welcome! This is part two of a blog post series on the binary search tree data structure.

If you have not real my previous post, I highly recommend you to read introduction to the binary search tree before proceeding.

Finally, in this post, we will be writing our own binary search tree implementation, dissecting the key operations and understanding exactly how the binary search tree works under the scenes.

Binary Search Tree Implementation API

Attached below is our Binary search tree interface. The available public methods are

  • add(data): Should be common sense that consumers should be able to add items to the tree.
  • remove(data): Search for the data to remove and remove it from the tree.
  • max(): Return the “largest” data from the set by traversing to the far right of the tree.
  • min(): Return the “smallest” data from the set by traversing to the far left of the tree.

Re-iterating the importance of assumptions, it is because of the rules, that we are able to implement the min() and max() method in a sound and cohesive manner. Once you have gotten the hang of Binary Search Trees, feel free to extend the API and add your own methods.Continue reading

Introduction to the Binary Search Tree in JavaScript

What is the Binary Search Tree?

The binary search tree is a fundamental data structure in computer science. Just as with all other data structures and algorithms, the binary search tree is built on specific rules and assumptions. These assumptions, enable us to examine the shortcomings of previous data structures such as the linked list, and improve the search time. In this article, we will explore the binary search tree data structure and some of the searching algorithms used.

Please do take note that this is part one of a series of posts on the Binary Search Tree. The Implementation details will be provided in part 2, along with a detailed guide on how to implement the binary search tree.

Why do we need assumptions?

Well, it is because of these assumptions that we are able to get such high performance from certain data structures. Assumptions enable us to code specifically. For example, if we only had forks to eat food with, it would definitely be inconvenient to eat rice. Hope you understood my analogy in the previous sentence. As the same suggests, the binary search tree enables us to search for items much more quickly. If we didn’t have the binary search tree, we might have to just do a brute force search. The time complexity for the brute force search would be O(n). With binary search trees, it is possible to reduce the search time to O(log n). In the worst case situation however, the search time can be the same as with a brute-force search O(n).

Key Features

Now that we understand the need for assumptions, we will examine the key features.

  • Each piece of data that is part of the tree is referred as a node.
  • The  root node is the first element inserted, or the one that sits at the top of the tree.
  • Each node has at most, two children.
  • Nodes at the bottom of the tree without any child are called leaf nodes.
  • The left node has a key (or value) that is less than the parent node.
  • The right node has a key (or value)  greater than the parent node.

Continue reading

c++ const keyword explained in detail

c++ const is used very commonly. If you have ever written any code in C++, you will definitely have used const and come across it. Needless to say, is a very useful and important feature. Using c++ const can greatly improve the robustness of your code. It is also a great way to document to other developers that the object marked as const should not be modified. On the other hand, omission of the const keyword in places where it is needed results in more brittle, error-prone code.

In a nutshell, const  (constant) means that a property or value cannot change. 

Continue reading

JavaScript Fundamentals – Introduction to the JavaScript function – Part 1

This time, I want to focus a little bit on a more preliminary topic. Functions in JavaScript are one of the main building blocks. Bits of code inserted into functions makes code readable, therefore, more maintainable. Imagine a JavaScript program where everything is written in the global scope and the code spans over tens of thousands of lines. Nobody would want to maintain code like that!

Separating code into smaller parts by placing them inside of a function (based on operation) allows developers to easily look up which part is responsible for certain features, making the debugging process much more pleasant.

In this post, we will be going through some of the important basics of the JavaScript function. Right now, i have other topics as higher priority. Therefore, if you want more posts dedicated to JavaScript functions or similar, related topics, please drop a comment and let me know.

Continue reading

Strings (std::string) Demystified in C++ (including concatenation)

What is a String?

It is simply just a word. Strings are all around us. Like dog, cat, etc. A more formal definition would be the following: it is a series of characters that has a varying length.
Needless to say, strings are one of the most important concepts in programming.
Before we dive in, I would like to address those experienced only in high level languages such as Java, Python or Javascript. In C, there is no built-in support for strings.  Fortunately, the C++ standard library provides users with a string class. C++ developers probably let out a sigh of relief, since they didn’t have to write implementations for the equals operator or the 

size()

method.

Continue reading

Introduction to Javascript closure

Introduction

JavaScript closure is one of the most important concepts if you want to go anywhere with JavaScript. It is as important as pointers in C/C++. Closures empower JavaScript developers to write better code. So, if you want to become a better JavaScript developer, learn closures.With great power comes great responsibility however. Therefore, if misused, they can create a nightmare. In order to learn functional programming in JavaScript, developers first need to have a solid understanding of how JavaScript closure works.Continue reading