# 3. Connecting the dots — Big O and Trees Data Structure

In the previous article, we saw how linked list data structure works. Let us discuss “Trees” data structure in this one. Trees are used to store** non linear hierarchical** data such as an organization chart in a company. You can consider a linked list as a form of a tree where you have a node with a pointer. In a binary tree, you will have a node with two pointers, a left and a right pointer.

# Basics:

Before we get started, let us see some of the basics concepts of a tree data structure and kinds of trees.

**Root node —**The top node of a tree is called the root node.**Parent node —**When a root node is connected to other nodes, it’s called a parent**Child****node —**Every parent can have one or two child nodes under them. However, every child has only one parent node.**Leaf node —**A node that does not have a child is called a leaf node.**Siblings —**Nodes with same parent are called siblings**Edge —**is the connection between two nodes or a node and a leaf.- The sequence of nodes along the edges of a tree is referred as a
**Path.**

A tree can point to one or many items. Since we are going to be considering only with 2 items below a root node, we call them as ** binary tree**. Below is the example of a simple binary tree.

# Binary Tree types:

There are three kinds of a binary tree

**Perfect tree: ***when a tree has child below every node completely filled. A perfect tree will** always** will full and complete.*

**Full tree: ***Full tree has two nodes or no nodes.*

**Complete tree:** *all the levels are completely filled except possibly the lowest one, which is filled from the left.*

# Binary Search Tree

So far we talked about binary trees. Binary search tree (BST) is special category of binary tree where all the values on the **right side **or** right subtrees **of every node will be** greater** than the

**left side**or

**left subtrees**

*.*

Take a look at the below BST: At the root node (i.e., 11), all the items in the right sub tree are greater (15, 13, 20) and on the left, every value is less (7,5,9). This property of BST holds true even if the tree grows in size. Also, this tree is also a balanced tree.

Note: Binary search only works when you have values sorted.

# Big O and BST

Take a look at the example below. When we have a single node, it would take one operation (2¹-1=1). If we have a tree with 3 levels, it would take three operations or steps to find a value where we can also drop the constant. If we need find 9 from this tree below these are the steps we will perform.

- Compare 9 with root element.
- Root element is greater than the 9, we move to the left hand side of the node.
- Check if 7 is greater. Since is 7 < 9 we know 9 is on the right hand side.

Here we divided the tree and we looked only in the left side of the subtree. We completely ignored when we knew root element was larger than the number we were searching. This is called **divide** and** conquer.** This is why BST is very efficient when you have sorted data. The average time complexity BST operations for searching, inserting and deleting a for node in a **balanced tree** is **Big O (log N)**. BST works for strings too. Example: If you are looking for a word in a dictionary “Race”. You will probably search in the middle of the dictionary rather that flipping through the pages in the beginning. First you will drop everything before the alphabet “M”. Then you start using divide and conquer rule to find the word you are looking for.

**Unbalanced tree **it would be worst case** O (n) **for the same operations as we cannot use divide and conquer here. The traversal here will be similar to that of Linked list.

# Create a Class Node and BST:

## Inserting a node:

Here is a code example to insert a node in the left side.

class BinarySearchTree {

constructor() {

this.root = null

}insert(value) {// create a new node

const newNode = new Node(value)

// scenario 1: if there root item is null then add new node to root

if (this.root === null) {

this.root = newNode

return this

}

let temp = this.root// we do not know where to insert the value so we use while loop to iterate over

while(true) {// if the new value and the value in the tree are the same return undefined

if (newNode.value === temp.value) return undefined//if the new node vale is less than the root then go left

if (newNode.value < temp.value) {

if (temp.left === null) {

temp.left = newNode// if this case is the case then return this

return this

}

temp = temp.left

} else {// if the value is greater than the root node then go right and insert the value

if (temp.right === null) {

temp.right = newNode

return this

}

temp = temp.right

}

}

}

}

## Traversing a node:

Here is a code example to look for a value in the tree and for a value that is not there in the tree.

// traversing a tree using contains()contains(value) {// if root is equal null, then it will return false

if (this.root === null) return false// starting temp at the top

let temp = this.root

while(temp) {// if it's less than we are going to traverse through the left sub tree

if (value < temp.value) {

temp = temp.left

//if it's greater than we are going to traverse through the right sub tree

} else if (value > temp.value) {// if temp = value on the right will go through the while loop belowtemp = temp.right

} else {// if it's equal, then it returns true

return true

}

}// if temp is equal to null then it will break the loop and return false

return false

}

}

// To find the minimum value

minimumValueInaNode(currentNode) {// the minimum value in a BST will be in the left side of a tree or a sub tree and we loop through it

while(currentNode.left) {

currentNode = currentNode.left

}

return currentNode

}

}let myTree = new BinarySearchTree()

myTree.insert(11)

myTree.insert(7)

myTree.insert(15)

myTree.insert(5)

myTree.insert(9)

myTree.insert(13)

myTree.insert(20)myTree.minimumValueInaNode(myTree.root)

//myTree.minimumValueInaNode(myTree.root.right)

Here when we look for the right side sub tree value, it will return 13.

With that, we covered an interesting non linear data structure.

To summarize, Binary search trees are very efficient when it comes to searching a balanced tree and will have *time complexities of **Big O(log n)** or *** Big O(n)** depending on the type of tree.

If you like this article, please follow me and give a clap!

# Resources:

Data structures and algorithms with JavaScript, Learning JavaScript Data Structures and Algorithms, Grokking Algorithms, , *algorithm** , **wikipedia**.*