In this post I’ll provide some code for a general tree data structure in Javascript. I found a lot of packages on npm that provided binary trees, red-black trees, and tries [sic], but nothing that provided a general tree data structure. As with most implementations of data structures that I’ve seen, this implementation defines a Node object, and the large scale structure that we’re interested in, a Tree object. The Node object knows about other Node objects, specifically it’s parent and children. The Tree object is responsible for connecting these nodes in a tree structure. We could use a very, very similar Node object to build a different kind of tree, or a linked list, or a stack, or whatever.

The Node Object

Here, our Node object is initialized with its data and parent. It knows how to add a new child, and report whether or not it is root.

var Node = function( data, parent ) {
  this.data = data || null
  this.parent = parent || null
  this.children = []
}
Node.prototype.add_child = function( data ) {
  this.children.push( new Node( data, this.data ) )
}
Node.prototype.is_root = function() {
  if( this.parent == null ) {
    return true
  } else {
    return false
  }
}

The Tree Object

The tree object is able to use its Tree::add_path() method to add a new branch of nodes using a space-delimited path. This method uses the Node::add_child() method internally.

var Tree = function() {
  this.root = new Node()
}
Tree.prototype.add_path = function( path ) {
  var ptr = this.root
  var parts = path.split(' ')
  for( var i=0 ; i < parts.length ; i++ ) {
    if( ptr.data == parts[i] ) {
      next = _.filter( ptr.children, function( child ) {
        if( child.data == parts[i+1] ) {
          return true
        } else {
          return false
        }
      })
      if( next.length == 1 ) {
        ptr = next.shift()
      }
    } else {
      ptr.add_child( parts[i] )
      ptr = _.last( ptr.children )
    }
  }
}