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

trees data structure

Basics:

basic terms of tree
simple binary tree

Binary Tree types:

Kinds of binary tree

Binary Search Tree

binary search tree

Big O and BST

BST time complexity
Unbalanced tree which has only right side of the the tree

Create a Class Node and BST:

Creating a BST

Inserting a node:

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
}
}
}
}
node inserted

Traversing a node:

// 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 below
temp = 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
}
}
Traversing through a BST
// 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)
least value in a tree

Resources:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store