Hello.. 🙂 Are you ready for some Data structures Blablabla.. ? If yes then in this post am going to share my mind on yet another data structure called Trees for that matter Binary Search Trees BST. Trees are totally different from Arrays, Stacks and Queues but they definitely have a lot in common in terms of codes and Algorithms on these structures. let’s take a look at Trees.

Trees: A Data Structure Tree is nothing but a real life inverted Tree. Technically we define a Data Structure tree to be a non linear data structure that has a node which has a root that consist of zero or more links or connection. A tree must have a root otherwise it’s definitely not a Data structure tree, i just don’t know how to call that one. so this abstract tree we are talking about has a root that links to other nodes called Children(leaf) or Descendants(leaf) these two are connected or linked with what we call Edges(Branches). a data structure tree has some straight rules that makes it what it is.

1. A tree must have a root Node
2. The Children of the of tree are from a parent and they can not have two parents at a time,
3. Every node under a child is called a grandchild of the parent node connecting to its parent.
4. A Tree should not have two roots
5. A tree has a height that determines how tail it is and a depth how deep does it’s root connects to the other nodes.

With the above in mind then it’s for sure you are looking at a tree or else we may be dealing with something else, may be a graph, let’s wait till we get there. I intentionally didn’t want to include any visual so that you can better conceptualize here and when you do more other research on these topics the picture will become clear enough. it works for me that way. try do it the hard way and finally check it really works. but am going to do so a bit for us to have a look.

so the above denotes what a tree is and not in data structures on the right that is not the kind of tree we’re talking about here because in our case we’re saying the root must have at most two children or descendants same way the connected Nodes in this case Parents should also have maximum of two down link as children and those children can also give birth to others if they want but it can only be two like those days Chinese rules. it’s just like a family tree but with special restrictions. sub trees can also be formed when a parent node has two complete children. there are different type of threes quite some number of them out there but we want to take a look at one popular one which is Binary Search Trees

Binary Search Trees is a special type of tree under Data Structures Trees that has their own Properties and Restrictions. Binary search trees are not hard to identify if we follow these following rules.

• Each node must have at most two children. Usually referred to as “left” and “right.”

• All trees must have a “root” node.

• The order of nodes values must be: 

  left child < parent < right child.

• Nodes might need re-ordering after each insert/delete operation to keep the 

  left ⇐ parent < right constraint.

Let’s now look at the implementation of a BST. this is not too far from the implementation of a linked-list, stack or queues.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return undefined;
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }
  find(value) {
    if (this.root === null) return false;
    let current = this.root,
      found = false;
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        found = true;
      }
    }
    if (!found) return undefined;
    return current;
  }
  contains(value) {
    if (this.root === null) return false;
    let current = this.root,
      found = false;
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }
    return false;
  }
}

//      12
//   6     14
// 3  7  10  18

var tree = new BinarySearchTree();
tree.insert(12);
tree.insert(6);
tree.insert(14);
tree.insert(10);
tree.insert(3);
tree.insert(18);
tree.insert(7);

we create a node and BinarySearchTree and some methods like insert, find and contains to perform some algorithms on our binary tree. there is a very important note when reading a binary Search Table. you will notice in that tree all the left sided of a node is less than their primary node or parent and on the right side of every node the values or element in those line are greater than their top connectors, this is among other one of the key points to remember about this type of tree. Not all but also in a BST the elements are already sorted which makes it easy for the insertion and searching to be done on them. Some terminologies to remember about trees in general.

Tree Terminologies

Node

A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to child nodes.

The node having at least a child node is called an internal node.

Edge

It is the link between any two nodes.

Root

It is the topmost node of a tree.

Height of a Node

The height of a node is the number of edges from the node to the deepest leaf (ie. the longest path from the node to a leaf node).

Depth of a Node

The depth of a node is the number of edges from the root to the node.

Height of a Tree

The height of a Tree is the height of the root node or the depth of the deepest node.

The Big O notation of a BST in it worse case scenario on Search, Insert and Delete is O(n) Linear but with a best case scenario of O(log n) which appear to be the best we can equally have when we miss out on a constant time which in many case not so easily achievable.  On BST we have O(n) Linear Space complexity.

These topics takes a while and different types of research before grabbing their concept so there is no need to worry if you read some post like mine and you don’t really get it. Kindly read more after this and I bet you your time here will not be a waste it will definitely be a chained memory for you when trying to understand from other sources.

All the Best and until the next post Stay safe 🙂