getSumInTree.js

gistfile1.txt

var _ = require('lodash');

/**
 * Instructions:
 * 
 * Write a solution in Node.JS that:
 *
 * Given an representation of a binary tree deserialized as string and a number, create a binary tree 
 * and return every path in the tree with sum of the nodes that is equals the given number. 
 * A path can start from any node and end at any node, i.e. they need not be root node and leaf node.
 * 
 *
 * Example: 
 * Input: 
 * tree = "1 5 # # 2 3 2 # # 7 # # 1 5 # # 1 # #"
 * number = 5
 *
 *
 * Respective binary tree for the given input:
 *        1
 *      /   \
 *    5      2
 *         /    \
 *        3       1    
 *       /  \    /  \
 *      2    7  5    1           
 *
 * Output: [ 0: [5], 1: [2, 3], 2: [3, 2], 3: [5], 4: [1, 2, 1, 1] ] 
 *
 *
 * Rules:
 * 1. Do not create global scope.  We have a test runner that will iterate on your function and run many fixtures through it.
 * 2. The left sub-tree has priority over the right sub-tree.
 *
 * Common Questions:
 * 1. What's a binary tree? A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. 
 * 2. What does the # mean? It means null nodes.
 * 3. Can I use outside packages to solve (e.g. NPM, Bower)?  Yes.  You can use any packages you want to solve the solution.
 * 4. Can I use google or outside resources (e.g. StackOverflow, GitHub)?  Yes.  Act as you would in your day job.
 * 5. How should I send my solution? You must send the solution by email to diego@tenfold.com cc'ing kessiler@tenfold.com.
 *  
 *
 *
 * @param tree is a string with the representation of tree 
 * @param number is an random number - Note: it can be a floating point
 * @return an array with the nodes values in it or an empty array
 */
exports.getSumInTree = function( tree, number) {
    var Node = function(val){
        this.value = val;
        this.left = null;
        this.right = null;
    }

    function BinaryTree(){
        this.root = null;
    }

    BinaryTree.prototype.push = function(val){
        var root = this.root;
        if(!root){
            root = new Node(val);
            return;
        }

        var currentNode = root;
        var lastNode = root;
        while(currentNode){
            if(!currentNode.left){
                currentNode.left = new Node(val);
                break;
            }else if(currentNode.left.val=="#"){
                if(currentNode.right.val=="#"){
                    currentNode = lastNode.right;
                }else{
                    currentNode = currentNode.right;
                }
            }else if(currentNode.left){
                lastNode = currentNode;
                currentNode = currentNode.left;
            }
            else if(!currentNode.right){
                currentNode.right = new Node(val);
                break;
            }else if(currentNode.right.val=="#"){
                currentNode = lastNode.right;
            }else if(currentNode.right){
                currentNode = currentNode.right;
            }
        }
    }

    var pushArray = function(arr,binT){        
        arr = arr.split(" ");

        for (var i = 0; i < arr.length; i++) {
            binT.push( arr[i]=="#" ? "#" : parseInt(arr[i]) );
        }

        return binT;
    }
    
    var binT = new BinaryTree();
    bitT = pushArray(tree,binT);

    var findSum = function (number,binT) {
        var output = [];

        var totalSum = 0;

        var currentNode = binT.root;
        var lastNode = binT.root;
        var nodeStack = [];

        while(currentNode){
            if((totalSum + currentNode.val) < 5){
                nodeStack.push([currentNote, currentNode.val]);
                totalSum += currentNode.val;
            } else if((totalSum + currentNode.val) == 5){
                nodeStack.push([currentNote, currentNode.val]);
                output.push(nodeStack);
                output = [];
                totalSum = 0;
            } else if((totalSum + currentNode.val) > 5){
                totalSum -= nodeStack.pop().val;
                if(nodeStack[nodeStack.length - 1]){
                    currentNode = nodeStack[nodeStack.length - 1];
                    return output;
                }
                if(nodeStack[nodeStack.length - 2]){
                    lastNode = nodeStack[nodeStack.length - 2];
                }else{
                    lastNode = binT.root;
                }
            }

            if(currentNode.left.val == "#"){
                if(currentNode.right.val=="#"){
                    if(nodeStack[nodeStack.length - 1]){
                    currentNode = nodeStack[nodeStack.length - 1];
                    return output;
                    }
                    if(nodeStack[nodeStack.length - 2]){
                        currentNode = nodeStack[nodeStack.length - 2];
                    }else{
                        currentNode = lastNode;
                    }
                }else{
                    lastNode = currentNode;
                    currentNode = currentNode.right;
                }
            }else if(currentNode.right.val == "#"){
                    if(nodeStack[nodeStack.length - 1]){
                        currentNode = nodeStack[nodeStack.length - 1];
                        return output;
                    }
                    if(nodeStack[nodeStack.length - 2]){
                        currentNode = nodeStack[nodeStack.length - 2];
                    }else{
                        currentNode = lastNode;
                    }
            }

        }
    }

    return findSum(number,binT);
}

var tree = "1 5 # # 2 3 2 # # 7 # # 1 5 # # 1 # #";
var number = 5;
this.getSumInTree(tree,number);