JS Binary Tree

binary-tree.js

'use strict';

class Node {
  constructor (val, left, right){
    this.val = val;
    this.left = left || null;
    this.right = right || null;
  }
}

class Tree {
  // build a new tree
  constructor (){
    this.head = null;
  }

  // add a value in the right place (left if minor, right if greater)
  add(val) {
    let node = new Node(val);
    if(!this.head){
      this.head = node;
      return this;
    }

    const _add = (current, val) => {
      let direction = 'right';
      if(val < current.val){
        direction = 'left';
      }

      if(!current[direction]){
        current[direction] = node;
        return this;
      }
      else {
        return _add(current[direction], val);
      }
    }

    return _add(this.head, val);
  }

  // traverse the Tree and compare values
  _get (node, val){
    if(!node) return null;
    if(node.val === val) return node;
    return val < node.val ? this._get(node.left, val) : this._get(node.right, val);
  }

  // get a node given a val
  get (val) {
    return this._get(this.head, val)
  }

  delete (val) {
    // find how to do that
  }

  // calculate the height of a subtree
  height (node) {
    if(!node) return 0;
    return Math.max(this.height(node.left), this.height(node.right)) + 1;
  }

  // calculate the number of nodes in the tree
  size (node) {
    if(!node) return 0;
    return this.size(node.left) + this.size(node.right) + 1;
  }

}

module.exports = Tree;

index.js

'use strict';

const BinaryTree = require('./binary-tree.js');

const myTree = new BinaryTree();

myTree
  .add(4)
  .add(2)
  .add(5)
  .add(3)
  .add(1);

// find a node with val 2
const node2 = myTree.get(2);
console.log(`Node with val 2 is: `, node2);

// count the element of the tree
const allTreeSize = myTree.size(myTree.get(4));
console.log(`The size of the whole tree is: ${allTreeSize}`);

const subTreeSize = myTree.size(node2);
console.log(`The size of the tree starting from node2 is: ${subTreeSize}`);

// count the height of the tree
const allTreeHeight = myTree.height(myTree.get(4));
console.log(`The height of the whole tree is: ${allTreeHeight}`);

const subTreeHeight = myTree.height(node2);
console.log(`The height of the tree starting from node2 is: ${subTreeHeight}`);

package.json

{
  "name": "binary-tree",
  "version": "1.0.0",
  "description": "This is a draft implementation of a Binary Tree in Javascript.",
  "main": "index.js",
  "scripts": {
    "test": "mocha spec.js",
    "start": "node index.js"
  },
  "author": "Matteo Scandolo",
  "license": "Apache-2.0",
  "devDependencies": {
    "chai": "^3.5.0",
    "mocha": "^2.5.3"
  }
}

REAME.md

Binary Tree Implementation

This is a draft implementation of a Binary Tree in Javascript.

No libraaries are used to define the Tree, but mocha and chai are used to test the code, so you should execute npm install before running tests.

The BinaryTree implementation is defined in binary-tree.js, example usages are in index.js (too see them use npm start), test are defined in spec.js and you can execute them with npm test;

TODO

[ ] Implement delete function

spec.js

'use strict';

/* global describe, beforeEach, it */

const chai = require('chai');
const expect = chai.expect;

const BinaryTree = require('./binary-tree.js');

describe('The BinaryTree Class', () => {

  let tree;

  beforeEach(() => {
    tree = new BinaryTree();
  });

  it('should have an add function', () => {
    expect(tree.add).to.be.instanceof(Function);
  });

  describe('when adding an element', () => {
    beforeEach(() => {
      tree.add(5);
    });

    it('should add to the left', () => {
      tree.add(3);
      expect(tree).to.deep.equal({
        head: {
          val: 5,
          left: {
            val: 3,
            left: null,
            right: null
          },
          right: null
        },
      });
    });

    it('should add to the right', () => {
      tree.add(7);
      expect(tree).to.deep.equal({
        head: {
          val: 5,
          left: null,
          right: {
            val: 7,
            left: null,
            right: null
          },
        },
      });
    });
  });

  describe('give a tree', () => {
    beforeEach(() => {
      tree
        .add(4)
        .add(2)
        .add(5)
        .add(3)
        .add(1);
    });

    it('should get an element given the value', () => {
      const node = tree.get(2);
      expect(node).to.deep.equal({
        val: 2,
        left: {
          val: 1,
          left: null,
          right: null
        },
        right: {
          val: 3,
          left: null,
          right: null
        }
      })
    });

    it('should calculate the tree size', () => {
      const head = tree.get(4);
      const size = tree.size(head);
      expect(size).to.equal(5);
    });

    it('should calculate a sub-tree size', () => {
      const node = tree.get(2);
      const size = tree.size(node);
      expect(size).to.equal(3);
    });

    it('should calculate the tree height', () => {
      const head = tree.get(4);
      const height = tree.height(head);
      expect(height).to.equal(3);
    });

    it('should calculate a sub-tree height', () => {
      const node = tree.get(2);
      const height = tree.height(node);
      expect(height).to.equal(2);
    });
  });
});