Skip to content

Instantly share code, notes, and snippets.

@bhumit070
Created April 8, 2022 08:53
Show Gist options
  • Save bhumit070/89a7c04edcbc78d291159da5ae88804f to your computer and use it in GitHub Desktop.
Save bhumit070/89a7c04edcbc78d291159da5ae88804f to your computer and use it in GitHub Desktop.
BST add and delete
class Node {
constructor(value) {
this.value = value
this.left = null
this.right = null
}
}
class Tree {
constructor() {
this.root = null
}
insert(value, node = this.root) {
if (!this.root) {
this.root = new Node(value)
return
} else if (value > node.value && node.right == null) {
node.right = new Node(value)
} else if (value > node.value) {
return this.insert(value, node.right)
} else if (value < node.value && node.left == null) {
node.left = new Node(value)
return
} else if (value < node.value) {
return this.insert(value, node.left)
}
}
findValue(value, node = this.root) {
if (!node) return false
if (node.value === value) {
return true
}
if (value > node.value) {
node = node.right
return this.findValue(value, node)
}
if (value < node.value) {
node = node.left
return this.findValue(value, node)
}
}
findMinNode(node) {
if (node.left === null) {
return node
} else {
return this.findMinNode(node.left)
}
}
removeNode(node, value) {
if (node === null) return null
if (value === node.value) {
if (node.left === null && node.right === null) {
return null
} else if (current.left === null) {
return current.right
} else if (current.right === null) {
return current.left
} else {
let minNode = this.findMinNode(node.right)
node.value = minNode.value
node.right = this.removeNode(node.right, minNode.value)
return node
}
} else if (value > node.value) {
node.right = this.removeNode(node.right, value)
return node
} else if (value < node.value) {
node.left = this.removeNode(node.left, value)
return node
}
}
deleteNode(value) {
this.root = this.removeNode(this.root, value)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment