BFS and DFS (imperative style) with trees

graphStuff.js

// the intention was to make a gist, hence everything is put 
// into one file.

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

function treeNode(key) {
    this.key = key;
    this.left = null;
    this.right = null;

    this.addLeft = function(node) {
        this.left = node;
    };  

    this.addRight = function(node) {
        this.right = node;
    };  
}

function stack() {
    // for depth first
    // the stack is weird so as to  make the nodes go left to right 
    // a vanilla stack for test tree 1 (see below) would result in the (1,3,7,6,2,5,4)
    var internalArray = []; 
    var tempArray = []
    this.push = function(key) {
        tempArray.push(key);
    };  
    this.pop = function() {
        internalArray = internalArray.concat(tempArray.reverse());
        tempArray = []; 
        return internalArray.pop();
    };
}

function queue() {
    // for breadth first
    var internalArray = [];
    this.push = function(key) {
        internalArray.push(key);
    };
    this.pop = function() {
        return internalArray.shift();
    };
}

function search(dataStructure, rootNode, callbackFunction) {
    var structure = new dataStructure();
    var currentNode = rootNode;
    while (currentNode) {
        callbackFunction(currentNode.key);

        if (currentNode.left) {
            structure.push(currentNode.left);
        }

        if (currentNode.right) {
            structure.push(currentNode.right);
        }

        currentNode = structure.pop();
    }
}


// constructing the  test tree 1 
//       (1)
//       /  \
//     (2)   (3)
//    /  \    / \
//   (4) (5) (6) (8)
var root = new treeNode(1);
root.addLeft(new treeNode(2));
root.addRight(new treeNode(3));
root.left.addLeft(new treeNode(4));
root.left.addRight(new treeNode(5));
root.right.addLeft(new treeNode(6));
root.right.addRight(new treeNode(7));

// constructing the test tree 2
//           (1)
//          /   \ 
//         (2)   (12)
//        / \      \
//       /   \      \
//      (4)  (3)    (13)
//     /     /  \
//    (5)   (7) (8)
//    /    /
//   (6)  (9)

var root2 = new treeNode(1);
root2.addLeft(new treeNode(2));
root2.addRight(new treeNode(12));
root2.right.addRight(new treeNode(13));
root2.left.addLeft(new treeNode(4));
root2.left.addRight(new treeNode(3));
root2.left.left.addLeft(new treeNode(5));
root2.left.left.left.addLeft(new treeNode(6));
root2.left.right.addLeft(new treeNode(7));
root2.left.right.left.addLeft(new treeNode(9));
root2.left.right.addRight(new treeNode(8));

// function as argument to print key to screen
var printToScreen = function(stringToPrint) {
    console.log(stringToPrint);
}

var forMocha = (function() {
    var returnArray = [];
    return {
        clear: function() {
            returnArray = [];
        },
        addTo: function(key) {
            returnArray.push(key);
        },
        get: function() {
            return returnArray;
        }
    };
})();

describe('Depth First Search test', function() {
    it('test with root should return [1,2,4,5,3,6,7]', function() {
        search(stack, root, forMocha.addTo);
        expect(forMocha.get()).to.deep.equal([1, 2, 4, 5, 3, 6, 7]);
    });

    it('test with root2 should return [1,2,4,5,6,3,7,9,8,12,13]', function() {
        forMocha.clear();
        search(stack, root2, forMocha.addTo);
        expect(forMocha.get()).to.deep.equal([1, 2, 4, 5, 6, 3, 7, 9, 8, 12, 13]);
    });

});

describe('Breadth First Search test', function() {
    it('test with root should return [1,2,3,4,5,6,7]', function() {
        forMocha.clear();
        search(queue, root, forMocha.addTo);
        expect(forMocha.get()).to.deep.equal([1, 2, 3, 4, 5, 6, 7]);
    });

    it('test with root2 should return [1,2,12,4,3,13,5,7,8,6,9]', function() {
        forMocha.clear();
        search(queue, root2, forMocha.addTo);
        expect(forMocha.get()).to.deep.equal([1, 2, 12, 4, 3, 13, 5, 7, 8, 6, 9]);
    });
});