Skip to content

Instantly share code, notes, and snippets.

@simonkberg
Created January 28, 2017 18:04
Show Gist options
  • Save simonkberg/562e559d03e0cf4a98d2546be3ed67a0 to your computer and use it in GitHub Desktop.
Save simonkberg/562e559d03e0cf4a98d2546be3ed67a0 to your computer and use it in GitHub Desktop.
class BinaryTree {}
class EmptyBinaryTree extends BinaryTree {
isEmpty () { return true }
depth () { return 0 }
count () { return 0 }
inorder (fn) {}
preorder (fn) {}
postorder (fn) {}
contains (x) { return false }
insert (x) { return new BinaryTreeNode(x) }
remove (x) { return this }
}
const emptyTree = new EmptyBinaryTree()
class BinaryTreeNode extends BinaryTree {
constructor (
value,
left = emptyTree,
right = emptyTree
) {
super()
this.value = value
this.left = left
this.right = right
}
isEmpty () { return false }
depth () {
return 1 + Math.max(
this.left.depth(),
this.right.depth()
)
}
count () {
return 1 + this.left.count() + this.right.count()
}
inorder (fn) {
this.left.inorder(fn)
fn(this.value)
this.right.inorder(fn)
}
preorder (fn) {
fn(this.value)
this.left.preorder(fn)
this.right.preorder(fn)
}
postorder (fn) {
this.left.postorder(fn)
this.right.postorder(fn)
fn(this.value)
}
contains (x) {
return x === this.value ||
(x < this.value && this.left.contains(x)) ||
(x > this.value && this.right.contains(x))
}
insert (x) {
return new BinaryTreeNode(
this.value,
x < this.value
? this.left.insert(x)
: this.left,
x >= this.value
? this.right.insert(x)
: this.right
)
}
remove (x) {
if (x === this.value) {
const leftEmpty = this.left.isEmpty()
const rightEmpty = this.right.isEmpty()
if (leftEmpty && rightEmpty) {
return emptyTree
}
if (leftEmpty) {
return this.right
}
if (rightEmpty) {
return this.left
}
return new BinaryTreeNode(this.right.value, this.left)
}
if (this.contains(x)) {
return new BinaryTreeNode(
this.value,
x < this.value
? this.left.remove(x)
: this.left,
x > this.value
? this.right.remove(x)
: this.right
)
}
return this
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment