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

trees data structure


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()
least value in a tree




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