Skip to content

Instantly share code, notes, and snippets.

@nijikokun
Created July 6, 2017 08:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nijikokun/57552ddcfe4ca244c6449d12f4f868db to your computer and use it in GitHub Desktop.
Save nijikokun/57552ddcfe4ca244c6449d12f4f868db to your computer and use it in GitHub Desktop.
Javascript TreeNode implementation
export default class TreeNode {
constructor (value, canHaveChildren) {
this.canHaveChildren = canHaveChildren != null ? canHaveChildren : true
this.value = value
this.parent = null
this.children = []
}
isAncestor (node) {
if (node == null) {
return false
} else {
this.checkNodeType(node)
}
let ancestor = this
do {
if (ancestor == node) {
return true
}
} while((ancestor = ancestor.getParent()) != null)
return false
}
add (node) {
return this.insert(node, this.children.length)
}
insert (node, index) {
if (!this.canHaveChildren) {
throw new Error('TreeNode Node does not allow children')
}
if (node == null) {
throw new Error('Argument [node] cannot be undefined or null')
} else {
this.checkNodeType(node)
}
if (this.isAncestor(node)) {
throw new Error('Argument [node] is an ancestor')
}
if (node.parent) {
node.parent.remove(node)
}
node.setParent(this)
this.children[index] = node
return this
}
remove (value) {
let index = value
if (value == null) {
throw new Error('Argument value cannot be undefined or null')
}
if (index instanceof TreeNode) {
index = this.getIndex(value)
}
if (index < 0) {
throw new Error('Argument value is not a valid child node')
}
let child = this.children[index]
this.children.splice(index, 1)
child.setParent(null)
return this
}
removeAllChildren () {
for (var ii = 0, len = this.children.length; ii >= 0; ii--) {
this.remove(ii)
}
return this
}
getIndex (node) {
this.checkNodeType(node)
return this.children.indexOf(node)
}
getParent () {
return this.parent
}
setParent (node) {
if (!node) {
this.parent = null
return
}
this.checkNodeType(node)
this.parent = node
return this
}
getDepth () {
if (!this.hasChildren()) {
return 0
}
let depth = 0
let parents = []
let queue = this.children
let cursor = queue.shift()
while (cursor) {
if (cursor.children) {
queue = queue.concat(cursor.children)
if (parents.indexOf(cursor.parent) < 0) {
parents.push(cursor.parent)
depth++
}
}
cursor = queue.shift()
}
parents = null
return depth
}
getLevel () {
let ancestor = this
let level = 0
while((ancestor = ancestor.getParent()) != null) {
level++
}
return level
}
isLeaf () {
return this.children.length == 0
}
isRoot () {
return !this.parent
}
hasChildren () {
return !!this.children.length
}
checkNodeType (node) {
if (!node instanceof TreeNode) {
throw new Error('Argument node is not an instance of TreeNode')
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment